aboutsummaryrefslogtreecommitdiff
path: root/most_beautiful_item_query.py
blob: abf8d533c948389904b6e8681eed4f973dcdb1d4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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]))