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.
This Java solution operates by first sorting the items by their prices then iteratively building a list of maximum beauties at each price point. The binary search facilitates efficient queries, dramatically reducing potential computational overhead.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int *)a) - (*(int *)b);
6}
7
8int* coordinateCompress(int *values, int size, int *newSize) {
9 int *sortedValues = (int *)malloc(sizeof(int) * size);
10 for (int i = 0; i < size; i++) sortedValues[i] = values[i];
11 qsort(sortedValues, size, sizeof(int), compare);
12
13 int *compressedValues = (int *)malloc(sizeof(int) * size);
14 int last = -1;
15 *newSize = 0;
16 for (int i = 0; i < size; i++) {
17 if (i == 0 || sortedValues[i] != last) {
18 compressedValues[(*newSize)++] = sortedValues[i];
19 last = sortedValues[i];
20 }
21 }
22 free(sortedValues);
23 return compressedValues;
24}
25
26int findIndex(int *arr, int size, int value) {
27 int left = 0, right = size - 1;
28 while (left <= right) {
29 int mid = left + (right - left) / 2;
30 if (arr[mid] <= value) {
31 left = mid + 1;
32 } else {
33 right = mid - 1;
34 }
35 }
36 return right;
37}
38
39int* maxBeautyWithCompression(int **items, int itemsSize, int *itemsColSize, int *queries, int queriesSize, int *returnSize) {
40 int *allPrices = (int *)malloc(sizeof(int) * (itemsSize + queriesSize));
41 for (int i = 0; i < itemsSize; i++) allPrices[i] = items[i][0];
42 for (int i = 0; i < queriesSize; i++) allPrices[itemsSize + i] = queries[i];
43
44 int newPricesSize;
45 int *compressedPrices = coordinateCompress(allPrices, itemsSize + queriesSize, &newPricesSize);
46
47 int *dp = (int *)calloc(newPricesSize, sizeof(int));
48 for (int i = 0; i < itemsSize; i++) {
49 int idx = findIndex(compressedPrices, newPricesSize, items[i][0]);
50 if (dp[idx] < items[i][1]) {
51 dp[idx] = items[i][1];
52 }
53 }
54
55 for (int i = 1; i < newPricesSize; i++) {
56 if (dp[i] < dp[i - 1]) {
57 dp[i] = dp[i - 1];
58 }
59 }
60
61 int *result = (int *)malloc(sizeof(int) * queriesSize);
62 for (int i = 0; i < queriesSize; i++) {
63 int idx = findIndex(compressedPrices, newPricesSize, queries[i]);
64 result[i] = idx >= 0 ? dp[idx] : 0;
65 }
66
67 free(allPrices);
68 free(compressedPrices);
69 free(dp);
70 *returnSize = queriesSize;
71 return result;
72}
73
74int main() {
75 int *items[] = { (int[]){1, 2}, (int[]){3, 2}, (int[]){2, 4}, (int[]){5, 6}, (int[]){3, 5} };
76 int queries[] = {1, 2, 3, 4, 5, 6};
77 int itemsSize = 5;
78 int queriesSize = 6;
79 int itemsColSize = 2;
80 int returnSize;
81 int *result = maxBeautyWithCompression(items, itemsSize, &itemsColSize, queries, queriesSize, &returnSize);
82 for (int i = 0; i < returnSize; i++) {
83 printf("%d ", result[i]);
84 }
85 free(result);
86 return 0;
87}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.