Description
You are given n item's value and label as two integer arrays values and labels. You are also given two integers numWanted and useLimit.
Your task is to find a subset of items with the maximum sum of their values such that:
- The number of items is at most
numWanted.
- The number of items with the same label is at most
useLimit.
Return the maximum sum.
Example 1:
Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
Output: 9
Explanation:
The subset chosen is the first, third, and fifth items with the sum of values 5 + 3 + 1.
Example 2:
Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2
Output: 12
Explanation:
The subset chosen is the first, second, and third items with the sum of values 5 + 4 + 3.
Example 3:
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1
Output: 16
Explanation:
The subset chosen is the first and fourth items with the sum of values 9 + 7.
Constraints:
n == values.length == labels.length1 <= n <= 2 * 1040 <= values[i], labels[i] <= 2 * 1041 <= numWanted, useLimit <= n
Solutions
Solution 1
PythonJavaC++GoTypeScript
class Solution:
def largestValsFromLabels(
self, values: List[int], labels: List[int], numWanted: int, useLimit: int
) -> int:
ans = num = 0
cnt = Counter()
for v, l in sorted(zip(values, labels), reverse=True):
if cnt[l] < useLimit:
cnt[l] += 1
num += 1
ans += v
if num == numWanted:
break
return ans(code-box)
class Solution {
public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
int n = values.length;
int[][] pairs = new int[n][2];
for (int i = 0; i < n; ++i) {
pairs[i] = new int[] {values[i], labels[i]};
}
Arrays.sort(pairs, (a, b) -> b[0] - a[0]);
Map<Integer, Integer> cnt = new HashMap<>();
int ans = 0, num = 0;
for (int i = 0; i < n && num < numWanted; ++i) {
int v = pairs[i][0], l = pairs[i][1];
if (cnt.getOrDefault(l, 0) < useLimit) {
cnt.merge(l, 1, Integer::sum);
num += 1;
ans += v;
}
}
return ans;
}
}(code-box)
class Solution {
public:
int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
int n = values.size();
vector<pair<int, int>> pairs(n);
for (int i = 0; i < n; ++i) {
pairs[i] = {-values[i], labels[i]};
}
sort(pairs.begin(), pairs.end());
unordered_map<int, int> cnt;
int ans = 0, num = 0;
for (int i = 0; i < n && num < numWanted; ++i) {
int v = -pairs[i].first, l = pairs[i].second;
if (cnt[l] < useLimit) {
++cnt[l];
++num;
ans += v;
}
}
return ans;
}
};(code-box)
func largestValsFromLabels(values []int, labels []int, numWanted int, useLimit int) (ans int) {
n := len(values)
pairs := make([][2]int, n)
for i := 0; i < n; i++ {
pairs[i] = [2]int{values[i], labels[i]}
}
sort.Slice(pairs, func(i, j int) bool { return pairs[i][0] > pairs[j][0] })
cnt := map[int]int{}
for i, num := 0, 0; i < n && num < numWanted; i++ {
v, l := pairs[i][0], pairs[i][1]
if cnt[l] < useLimit {
cnt[l]++
num++
ans += v
}
}
return
}(code-box)
function largestValsFromLabels(
values: number[],
labels: number[],
numWanted: number,
useLimit: number,
): number {
const n = values.length;
const pairs = new Array(n);
for (let i = 0; i < n; ++i) {
pairs[i] = [values[i], labels[i]];
}
pairs.sort((a, b) => b[0] - a[0]);
const cnt: Map<number, number> = new Map();
let ans = 0;
for (let i = 0, num = 0; i < n && num < numWanted; ++i) {
const [v, l] = pairs[i];
if ((cnt.get(l) || 0) < useLimit) {
cnt.set(l, (cnt.get(l) || 0) + 1);
++num;
ans += v;
}
}
return ans;
}(code-box)
