Largest Values From Labels
Problem
You have n items, each with a value and a label. Pick a subset to maximize the total value subject to two rules: choose at most numWanted items in total, and choose at most useLimit items sharing the same label. Return the largest achievable sum.
values = [9, 8, 8, 7, 6], labels = [0, 0, 0, 1, 1], numWanted = 3, useLimit = 224def largest_vals_from_labels(values, labels, num_wanted, use_limit):
items = sorted(zip(values, labels), reverse=True)
used = {}
total = 0
picked = 0
for value, label in items:
if picked == num_wanted:
break
if used.get(label, 0) < use_limit:
total += value
used[label] = used.get(label, 0) + 1
picked += 1
return totalfunction largestValsFromLabels(values, labels, numWanted, useLimit) {
const items = values.map((v, i) => [v, labels[i]]);
items.sort((a, b) => b[0] - a[0]);
const used = new Map();
let total = 0, picked = 0;
for (const [value, label] of items) {
if (picked === numWanted) break;
if ((used.get(label) || 0) < useLimit) {
total += value;
used.set(label, (used.get(label) || 0) + 1);
picked++;
}
}
return total;
}class Solution {
public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
int n = values.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> values[b] - values[a]);
Map<Integer, Integer> used = new HashMap<>();
int total = 0, picked = 0;
for (int j = 0; j < n; j++) {
if (picked == numWanted) break;
int label = labels[idx[j]];
if (used.getOrDefault(label, 0) < useLimit) {
total += values[idx[j]];
used.put(label, used.getOrDefault(label, 0) + 1);
picked++;
}
}
return total;
}
}int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
int n = values.size();
vector<pair<int,int>> items;
for (int i = 0; i < n; i++) items.push_back({values[i], labels[i]});
sort(items.rbegin(), items.rend());
unordered_map<int,int> used;
int total = 0, picked = 0;
for (auto& it : items) {
if (picked == numWanted) break;
if (used[it.second] < useLimit) {
total += it.first;
used[it.second]++;
picked++;
}
}
return total;
}Explanation
We want the biggest total value, so the natural move is to grab the most valuable items first. The only thing stopping us is two rules: a total cap (numWanted) and a per-label cap (useLimit).
The plan is a clean greedy one: pair each value with its label, sort by value from high to low, then walk down the list taking items as long as both rules allow.
We keep a small lookup table used that counts how many items we have taken for each label. Before taking an item, we check used[label] < useLimit. If the label still has room, we add its value to total, bump its count, and increase picked. We stop entirely once picked reaches numWanted.
Taking the most valuable allowed item at every step is safe here: skipping a bigger item for a smaller one could never give a larger sum, so greedy is optimal.
Example: values = [9, 8, 8, 7, 6], labels = [0, 0, 0, 1, 1], numWanted = 3, useLimit = 2. Take 9 (L0) and 8 (L0) — label 0 is now full. Skip the third 8 (L0), take 7 (L1). That is 3 items: 9 + 8 + 7 = 24.