diff options
Diffstat (limited to 'most_beautiful_item_query.py')
-rw-r--r-- | most_beautiful_item_query.py | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/most_beautiful_item_query.py b/most_beautiful_item_query.py new file mode 100644 index 0000000..abf8d53 --- /dev/null +++ b/most_beautiful_item_query.py @@ -0,0 +1,36 @@ +# 2070. Most Beautiful Item for Each Query +from bisect import bisect + +""" +you are given a 2d integer array 'items' where 'items[i] = [price_i, +beauty_i]' denotes the price and beauty of an item respectively. you are also +given a 0-indexed integer array 'queries'. for each 'queries[i]' you want to +determine the maximum beauty of an item whose price is less than or equal to +'queries[i]'. if no such item exists, then the answer to this query is 0. +return an array 'answer' of the same length as 'queries' where 'answer[i]' is +the answer to the i'th query. +""" + + +class Solution(object): + def maximumBeauty(self, items, queries): + """ + :type items: List[List[int]] + :type queries: List[int] + :rtype: List[int] + """ + items = sorted(items + [[0, 0]]) + for i in range(len(items) - 1): + items[i + 1][1] = max(items[i][1], items[i + 1][1]) + return [items[bisect(items, [q + 1]) - 1][1] for q in queries] + + +if __name__ == "__main__": + obj = Solution() + print( + obj.maximumBeauty( + items=[[1, 2], [3, 2], [2, 4], [5, 6], [3, 5]], queries=[1, 2, 3, 4, 5, 6] + ) + ) + print(obj.maximumBeauty(items=[[1, 2], [1, 2], [1, 3], [1, 4]], queries=[1])) + print(obj.maximumBeauty(items=[[10, 1000]], queries=[5])) |