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.
The algorithm first sorts the items based on their price. While traversing through the sorted list, it maintains the maximum beauty for each price. For each query, a binary search is executed on this list of prices to fetch the corresponding maximum beauty. This method ensures optimal handling of both items and queries given constraints.
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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] MaxBeautyWithCompression(int[][] items, int[] queries) {
6 var priceSet = new SortedSet<int>();
7 foreach (var item in items) priceSet.Add(item[0]);
8 foreach (var query in queries) priceSet.Add(query);
9
10 var prices = new List<int>(priceSet);
11 var dp = new Dictionary<int, int>();
12 foreach (var price in prices) dp[price] = 0;
13
14 foreach (var item in items) {
15 dp[item[0]] = Math.Max(dp[item[0]], item[1]);
16 }
17
18 int currentMax = 0;
19 foreach (var price in prices) {
20 currentMax = Math.Max(currentMax, dp[price]);
21 dp[price] = currentMax;
22 }
23
24 var result = new int[queries.Length];
25 for (int i = 0; i < queries.Length; i++) {
26 var index = prices.BinarySearch(queries[i]);
27 if (index < 0) index = ~index - 1;
28 result[i] = index >= 0 ? dp[prices[index]] : 0;
29 }
30
31 return result;
32 }
33
34 public static void Main(string[] args) {
35 var solution = new Solution();
36 int[][] items = new int[][] { new int[] {1,2}, new int[] {3,2}, new int[] {2,4}, new int[] {5,6}, new int[] {3,5} };
37 int[] queries = new int[] { 1, 2, 3, 4, 5, 6 };
38 int[] result = solution.MaxBeautyWithCompression(items, queries);
39 Console.WriteLine(string.Join(" ", result));
40 }
41}C# Hash and SortedSet are employed for index compression, allowing a reduced coordinate system upon which a dynamic array of maximum beauties can efficiently resolve queries using the BinarySearch feature for indexed price identification.