C++ Solution | Sorting
Solution\n\n Brute force approach would be : For each query, traverse the items and check the ones having price less than or equal to queries[i] and find the ma
**Solution**\n\n* Brute force approach would be : For each query, traverse the items and check the ones having price less than or equal to `queries[i]` and find the maximum beauty among these items - *O(QN)*.\n* Drawback of previous approach is, we have to traverse items multiple times. If we have found the answer for query say 80, we can find the answer for query 100 by only traversing the item with price in the range (80, 100] instead of checking all items in price range [0, 100].\n\n* If the items are sorted in increasing order of their price, then in the above example, for query 80 we will traverse the items only upto price 80 and then for 100 we will continue from the item where we would have left for 80.\n\n* The only problem is that the above method need the queries to be in increasing order. If query 80 comes after 100 then we don\'t have a way to use result for 100 to find the result for 80.\n\n* Hence, we will sort the queries, keeping their original index with them. Then process them in the same order.\n\n**Algorithm**\n\n1. Store each query `queries[i]` as a pair of {`queries[i]`, `i`} into the vector `queriesPair`.\n2. Sort `queriesPair` and `items` in ascending order.\n3. Iterate over `queriesPair`, find the maximum beauty of item having price less than `queriesPair[i].first`\n4. Store it in the `maxBeauty`.\n5. Store `maxBeauty` in the answer vector `ans` at index `queriesPair[i].second`.\n\n**Time Complexity**: \n\n- Sorting items takes NlogN\n- Sorting queries takes QlogQ\n- Iterating over each Item and query takes (N + Q)\n- Time Complexity : O(NlogN + QlogQ)\n\n```\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        vector<int> ans(queries.size());\n        \n        vector<pair<int ,int>> queriesPair;\n        for (int i = 0; i < queries.size(); i++) {\n            queriesPair.push_back({queries[i], i});\n        }\n        \n        sort(queriesPair.begin(), queriesPair.end());\n        sort(items.begin(), items.end());\n        \n        int itemIndex = 0, maxBeauty = 0;\n        for (int i = 0; i < queriesPair.size(); i++) {\n            int maxPriceAllowed = queriesPair[i].first;\n            int queryOriginalIndex = queriesPair[i].second;\n            \n            // Iterate over items, stop when the price exceeds query price or no item left\n            while (itemIndex < items.size() && items[itemIndex][0] <= maxPriceAllowed) {\n                maxBeauty = max(maxBeauty, items[itemIndex][1]);\n                itemIndex++;\n            }\n            \n            ans[queryOriginalIndex] = maxBeauty;\n        }\n        \n        return ans;\n    }\n};\n```
[]