Largest Values From Labels

We have a set of items: the i-th item has value values[i] and label labels[i].
Then, we choose a subset S of these items, such that:
|S| <= num_wanted
For every label L, the number of items in S with label L is <= use_limit.

Return the largest possible sum of the subset S.

Example 1:

Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
Output: 9
Explanation: The subset chosen is the first, third, and fifth item.

Example 2:

Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
Output: 12
Explanation: The subset chosen is the first, second, and third item.

Example 3:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
Output: 16
Explanation: The subset chosen is the first and fourth item.

Example 4:

Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
Output: 24
Explanation: The subset chosen is the first, second, and fourth item.

Note:

1. 1 <= values.length == labels.length <= 20000
2. 0 <= values[i], labels[i] <= 20000
3. 1 <= num_wanted, use_limit <= values.length

Solution: 

We need to sort the values and their labels in non-ascending order and then just choose the top num_wanted based on use_limit.

For use_limit we use a count array.

Code:

	class Solution {
	public:
	int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
	vector<pair<int, int>> v;
	for (int i=0; i<values.size(); i++){
	v.push_back(make_pair(values[i], labels[i]));
	}
	sort(v.rbegin(),v.rend());
	int sum =0;
	int countArr[20002] = {0};
	for (int i=0; i<v.size();++i){
	if(num_wanted==0) break;
	if (countArr[v[i].second] < use_limit){
	sum += v[i].first;
	countArr[v[i].second]++;
	num_wanted--;
	}
	}
	return sum;
	}
	};

view raw Largest Values From Labels hosted with ❤ by GitHub