Sponsored
Sponsored
In this approach, we perform the following steps:
Time Complexity: O((n + m) log n) where n = number of items and m = number of queries.
Space Complexity: O(n) for storing the processed items data.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6vector<int> maxBeautyForQueries(vector<pair<int, int>>& items, vector<int>& queries) {
7 sort(items.begin(), items.end());
8 vector<int> maxBeauty;
9 int currentMax = 0; for (const auto& item : items) {
10 currentMax = max(currentMax, item.second);
11 maxBeauty.push_back(currentMax);
12 }
13
14 vector<int> answer(queries.size());
15 for (size_t i = 0; i < queries.size(); ++i) {
16 int idx = upper_bound(items.begin(), items.end(), make_pair(queries[i], INT_MAX)) - items.begin() - 1;
17 answer[i] = (idx >= 0) ? maxBeauty[idx] : 0;
18 }
19 return answer;
20}
21
22int main() {
23 vector<pair<int, int>> items = {{1,2},{3,2},{2,4},{5,6},{3,5}};
24 vector<int> queries = {1, 2, 3, 4, 5, 6};
25 vector<int> result = maxBeautyForQueries(items, queries);
26 for (int res : result) {
27 cout << res << " ";
28 }
29 return 0;
30}This solution uses the C++ STL to manage pair-wise elements of items. After sorting, it preserves a running maximum of beauty for each price point. Binary searching through this vector allows rapid resolution for each query, ensuring swift data access by querying price indices directly.
Coordinate compression can be used to reduce problem complexity when dealing with large range values like prices. In this approach:
Time Complexity: O((n + m) log(n + m)) due to sorting during compression.
Space Complexity: O(n + m) for storing all price points and decision arrays.
This solution first compresses the range of prices into indexes, reducing the search space. A dynamic programming approach then determines the maximum beauty at each possible price point index, allowing quick lookup when answering queries. This methodology deals efficiently with large query ranges.