LeetCode //C - 1090. Largest Values From Labels

1090. Largest Values From Labels

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.length
• $1<=n<=2\ast 10^4$
• $0<=values[i],labels[i]<=2\ast 10^4$
• 1 <= numWanted, useLimit <= n

From: LeetCode Link: 1090. Largest Values From Labels

Solution:

Ideas:

sort items by value from largest to smallest, then greedily pick an item only if its label has not reached useLimit and total picked items is still under numWanted.

Code:

typedef struct {
int value;
int label;
} Item;

int cmp(const void* a, const void* b) {
Item* x = (Item*)a;
Item* y = (Item*)b;
return y->value – x->value; // descending by value
}

int largestValsFromLabels(int* values, int valuesSize, int* labels, int labelsSize, int numWanted, int useLimit) {
Item* items = (Item*)malloc(sizeof(Item) * valuesSize);

for (int i = 0; i < valuesSize; i++) {
items[i].value = values[i];
items[i].label = labels[i];
}

qsort(items, valuesSize, sizeof(Item), cmp);

int labelCount[20001] = {0};
int sum = 0;
int chosen = 0;

for (int i = 0; i < valuesSize && chosen < numWanted; i++) {
int lab = items[i].label;

if (labelCount[lab] < useLimit) {
sum += items[i].value;
labelCount[lab]++;
chosen++;
}
}

free(items);
return sum;
}