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.

&nbsp;
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.


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.


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.


&nbsp;
Constraints:


	n == values.length == labels.length
	1 &lt;= n &lt;= 2 * 104
	0 &lt;= values[i], labels[i] &lt;= 2 * 104
	1 &lt;= numWanted, useLimit &lt;= n


from collections import defaultdict
import heapq

class Solution:
    def largestValsFromLabels(
        self, values: list[int], labels: list[int], numWanted: int, useLimit: int
    ) -> int:

        # Add labels and values into the heap
        heap = [(-value, label) for value, label in zip(values, labels)]
        heapq.heapify(heap)

        # Initialize the hashmap
        used = defaultdict(int)

        # Initialize the result
        res = 0

        # Iterate until we have used a certain number or the heap is empty
        while numWanted > 0 and heap:

            # Pop a label and its value from the heap
            value, label = heapq.heappop(heap)

            # If we can use such label
            if used[label] < useLimit:

                # Add its value to the result
                res += -value

                # Increment its count in the hashmap
                used[label] += 1

                # Decrement the number of numbers we still want
                numWanted -= 1

        return res
class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        PriorityQueue<Pair<Integer, Integer>> maxHeap = 
            new PriorityQueue<>((a, b) -> Integer.compare(b.getKey(), a.getKey()));
        for(int i=0;i<values.length;i++) {
            maxHeap.add(new Pair<Integer, Integer>(values[i], labels[i]));
        }
        Map<Integer, Integer> labelLimitMap = new HashMap<>();
        int sum = 0;
        while(numWanted != 0) {
            int label = maxHeap.peek().getValue();
            if(labelLimitMap.containsKey(label)) {
                if(labelLimitMap.get(label) == useLimit) {
                    maxHeap.poll();
                } else {
                    labelLimitMap.put(label, labelLimitMap.get(label) + 1);
                    sum += maxHeap.poll().getKey();
                    numWanted--;
                }
            } else {
                labelLimitMap.put(label, 1);
                sum += maxHeap.poll().getKey();
                numWanted--;
            }
            // This Holds since at most numWanted is mentioned.
            if(maxHeap.isEmpty()) {
                return sum;
            }
        }
        return sum;
    }
}
class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
        // same label item should be less than uselimit
        priority_queue<pair<int,int>>q;  // this will give us maximum element because we need to maximise the sum 
        for(int i=0;i<values.size();i++)
        {
            q.push({values[i],i});
        }
        long long int ans=0;
        unordered_map<int,int>m;
        // we cant use more numbers than useLimit
        // storing each use labels in map to count the use limit of that number
        int i=0;
        while(i<numWanted)
        {
            int t=q.top().first;   //number 
            int ind=q.top().second; // labels index
            q.pop();
            if(m[labels[ind]]<useLimit)   // if less than count then include in our answer
            {
                ans+=t;
                m[labels[ind]]++;
                i++;
            }
            if(q.size()==0)
            {
                break;
            }
        }
        return ans;
    }
};
/**
 * @param {number[]} values
 * @param {number[]} labels
 * @param {number} numWanted
 * @param {number} useLimit
 * @return {number}
 */
var largestValsFromLabels = function(values, labels, numWanted, useLimit) {
    // this sortValues will create an addition array that keep track of the value idx after descending sort
    // which is useful to map the labels accordingly
    let sortValues = values.map((val, idx) => [val, idx]), sortLabels = []
    sortValues.sort((a, b) => b[0] - a[0])
    
    for (let [val, idx] of sortValues) {
        sortLabels.push(labels[idx])
    }
    values.sort((a, b) => b - a)
    labels = sortLabels
    
    let i = 0, map = {}, ans = 0
    while (i < values.length && numWanted > 0) {
        if (map[labels[i]]) map[labels[i]] ++
        else map[labels[i]] = 1
        
        if ((map[labels[i]]) <= useLimit) {
            ans += values[i]
            numWanted--
        }
        
        i++
    }
    
    return ans
    
};
Largest Values From Labels