We have a set of items: the i-th item has value values[i] and label labels[i].
Then, we choose a subset S of these items, such that:
|S| <= num_wanted
For every label L, the number of items in S with label L is <= use_limit.
Return the largest possible sum of the subset S.
Example 1:
Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth item.
Example 2:
Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
Output: 12
Explanation: The subset chosen is the first, second, and third item.
Example 3:
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
Output: 16
Explanation: The subset chosen is the first and fourth item.
Example 4:
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
Output: 24
Explanation: The subset chosen is the first, second, and fourth item.
Note:
1 <= values.length == labels.length <= 20000
0 <= values[i], labels[i] <= 20000
1 <= num_wanted, use_limit <= values.length
class Solution {
public int largestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit) {
//Initial thougth: chekc them by cur label and num_wanted, whcih has two ariables
//it is hard to control since we do not sorted them
//so instead sort the pair<value, label> by value
//them check num_wanted
PriorityQueue<pair> pq;
pq = new PriorityQueue<pair>((a, b)->( b.val-a.val));//sorted by the value(large to small)
for(int i = 0; i<values.length; i++){
pq.offer(new pair(values[i], labels[i]));
}
//Plus, we should remember the used label
HashMap<Integer, Integer> map = new HashMap<>();
int res = 0;
while(num_wanted>0 && !pq.isEmpty()){
pair p = pq.poll();
int used = map.getOrDefault(p.lab,0);
//System.out.println(used);
if(used < use_limit){
used++;
map.put(p.lab, used);
res+=p.val;
num_wanted--;
}
}
return res;
}
class pair{
int val;
int lab;
pair(int val, int lab){
this.val = val;
this.lab=lab;
}
}
}