Java | TreeMap | BinarySearch | similar problems
similar problems:\n1235. Maximum Profit in Job Scheduling https://leetcode.com/problems/maximum-profit-in-job-scheduling/\n2008. Maximum Earnings From Taxi http
similar problems:\n1235. Maximum Profit in Job Scheduling https://leetcode.com/problems/maximum-profit-in-job-scheduling/\n2008. Maximum Earnings From Taxi https://leetcode.com/problems/maximum-earnings-from-taxi/\n1353. Maximum Number of Events That Can Be Attended  https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/\n2054. Two Best Non-Overlapping Events https://leetcode.com/problems/two-best-non-overlapping-events/\n\nTreeMap\n```\nclass Solution {\n    public int[] maximumBeauty(int[][] items, int[] queries) {\n        int[] result = new int[queries.length];\n        Arrays.sort(items, (a, b) -> (a[0] - b[0]));\n        \n        TreeMap<Integer, Integer> map = new TreeMap<>(){{put(0, 0);}};\n        int currMax = 0;\n        for(int[] item : items) {\n            currMax = Math.max(currMax, item[1]);      //maintain largerst beauty so far\n            map.put(item[0], currMax);                 //store in treeMap\n        }\n        \n        for(int i = 0; i < queries.length; ++i)\n            result[i] = map.floorEntry(queries[i]).getValue();\n        \n        return result;\n    }\n}\n```\n\nBinarySearch:\n\n```\nclass Solution {\n    public int[] maximumBeauty(int[][] items, int[] queries) {\n        int[] result = new int[queries.length];\n        Arrays.sort(items, (a, b) -> (a[0] - b[0]));\n        \n        for(int i = 1; i < items.length; ++i)\n            items[i][1] = Math.max(items[i][1], items[i - 1][1]);\n\n        for(int j = 0; j < queries.length; ++j)\n            result[j] = binarySearch(items, queries[j]);\n        \n        return result;\n    }\n    \n    private int binarySearch(int[][] items, int target) {\n        int lo = 0, hi = items.length - 1;\n        while(lo < hi) {\n            int mid = (lo + hi + 1) >> 1;  //find rightmost item\n            if(items[mid][0] > target)\n                hi = mid - 1;\n            else\n                lo = mid;\n        }\n        return items[lo][0] <= target ? items[lo][1] : 0;\n    }\n}\n
[]