# Leetcode: Largest Values From Labels

Largest Values From Labels

<a href=”https://github.com/dennyzhang/code.dennyzhang.com/tree/master/problems/example“><img align=”right” width=”200″ height=”183″ src=”” /></a>

Similar Problems:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```// Blog link: https://code.dennyzhang.com/example
// Basic Ideas: Greedy
// Complexity: Time O(n*log(n)), Space O(n)
import "sort"
type Node struct {
value int
label int

}
func largestValsFromLabels(values []int, labels []int, num_wanted int, use_limit int) int {
res := 0
l := []Node{}
for i, _ := range values {
l = append(l, Node{values[i], labels[i]})
}
sort.Slice(l, func(i, j int) bool {
return l[i].value > l[j].value
})

m := map[int]int{}
for i, _ := range l {
if num_wanted == 0 {
break
}
if m[l[i].label] >= use_limit { continue }
// pick current value
res += l[i].value
m[l[i].label]++
num_wanted--
}
return res
}
```

<div style=”overflow: hidden;”>