Sort and Sweep
Rhymes with short and sweet :)\n\nWe sort items cheap-to-expensive, and then sweep the array and assign maximum beauty so far.\n\nThen, use a binary search to f
Rhymes with short and sweet :)\n\nWe sort items cheap-to-expensive, and then sweep the array and assign maximum beauty so far.\n\nThen, use a binary search to find the maximum beauty for the price.\n\n**C++**\n```cpp\nvector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& qs) {\n    sort(begin(items), end(items));\n    for (int i = 1; i < items.size(); ++i)\n        items[i][1] = max(items[i][1], items[i - 1][1]);\n    for (int i = 0; i < qs.size(); ++i) {\n        auto it = upper_bound(begin(items), end(items), vector<int>{qs[i], INT_MAX});\n        qs[i] = it == begin(items) ? 0 : (*prev(it))[1];\n    }\n    return qs;\n}\n```
[]