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;
}