[Python3] - Sort + Binary Search - Easy to understand
Intuition\n Describe your first thoughts on how to solve this problem. \nProblem said price is less than or equal so it means we can think about sorting by pric
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nProblem said `price is less than or equal` so it means we can think about sorting by `price` and then do binary search to find `price is less than or equal` to the `queries[j]`. But it is not only that simple. In here we have to find the maximum `beauty` for all the price less than or equal to `queries[j]`. Assume the highest `price` in `items` that is <= `queries[j]` is at index `i`. we can easily get that `max beauty = items[k][1] for 0 <= k <= i` \n- So we must find the max beauty in range from 0 to i for the `queries[j]`\n \n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Sort items by price - $O(nlogn)$\n- update the beauty for index i in items = `max(items[x] for x in range(i + 1))` - $O(n)$\n- for each query, binary search for the highest item which has price `<=` this query\'s value, then add to final result the `max beauty` in range `first query to current querry` - $O(nlogn)$\n\n# Complexity\n- Time complexity: $O(nlogn + n + nlogn)$ ~ $O(nlogn)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(1)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n        items.sort()\n        n = len(items)\n        res = []\n        for i in range(1, n):\n            items[i][1] = max(items[i][1], items[i - 1][1])\n\n        for q in queries:\n            l, r = 0, n - 1\n            while l <= r:\n                m = (l + r) >> 1\n                p, b = items[m]\n                if p > q: r = m - 1\n                else: l = m + 1\n            res.append(items[r][1] if r >= 0 else 0)\n        return res\n```
['Binary Search', 'Sorting', 'Python3']