# 1090. Largest Values From Labels

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. `1 <= values.length == labels.length <= 20000`
2. `0 <= values[i], labels[i] <= 20000`
3. `1 <= num_wanted, use_limit <= values.length`

``````class Solution {
public:
int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
int res = 0, n = values.size();
priority_queue<pair<int, int>> pq;
unordered_map<int, int> useMap;
for (int i = 0; i < n; ++i) {
pq.push({values[i], labels[i]});
}
while (num_wanted > 0 && !pq.empty()) {
int value = pq.top().first, label = pq.top().second; pq.pop();
if (++useMap[label] <= use_limit) {
res += value;
--num_wanted;
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1090

https://leetcode.com/problems/largest-values-from-labels/

https://leetcode.com/problems/largest-values-from-labels/discuss/312720/C%2B%2B-Greedy

https://leetcode.com/problems/largest-values-from-labels/discuss/313011/Question-Explanation-and-Simple-Solution-or-Java-or-100

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation