1090. Largest Values From Labels

There is a set of n items. You are given two integer arrays values and labels where the value and the label of the ith element are values[i] and labels[i] respectively. You are also given two integers numWanted and useLimit.

Choose a subset s of the n elements such that:

• The size of the subset s is less than or equal to numWanted.
• There are at most useLimit items with the same label in s.

The score of a subset is the sum of the values in the subset.

Return the maximum score of a subset s.

class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
        vector<pair<int, int>> A;
        int n = values.size(), res = 0;
        for(int i = 0; i < n; i++) {
            A.push_back({values[i], labels[i]});
        }
        sort(rbegin(A), rend(A));
        unordered_map<int, int> freq;
        for(int i = 0; i < n and numWanted; i++) {
            auto [v, l] = A[i];
            if(freq[l] == useLimit) continue;
            res += v;
            ++freq[l];
            --numWanted;
        }
        return res;
    }
};