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=”github.png” /></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;”>

<div style=”float: left; padding: 5px”> <a href=”https://www.linkedin.com/in/dennyzhang001“><img src=”linkedin.png” alt=”linkedin” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://github.com/dennyzhang“><img src=”github.png” alt=”github” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://www.dennyzhang.com/slack” target=”_blank” rel=”nofollow”><img src=”slack.png” alt=”slack”/></a></div>

</div>


Share It, If You Like It.

Leave a Reply

Your email address will not be published.