1090-largest-values-from-labels.adoc

1090. Largest Values From Labels

{leetcode}/problems/largest-values-from-labels/[LeetCode - 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 ⇐ values.length == labels.length ⇐ 20000

• 0 ⇐ values[i], labels[i] ⇐ 20000

• 1 ⇐ num_wanted, use_limit ⇐ values.length

思路分析

初看以为是回溯（回溯也可以，能通过大部分的测试），看答案之后，可以通过排序来解决。

再次想想，感觉回溯解决不了问题，它没办法保证首先选中的就是大数。

一刷

link:{sourcedir}/_1090_LargestValuesFromLabels.java[role=include]

参考资料

1. 1090. 受标签影响的最大值 - 官方题解