Pick Within Tag Limits

Medium

A warehouse holds n items: item i is worth values[i] and carries tag tags[i]. Choose a set of items with the largest total worth while following two rules: - the set has at most max_items items; - at most per_tag items share the same tag. Return the largest total worth of such a set.

Example 1

values=[7, 6, 5, 3], tags=[1, 1, 1, 2], max_items=3, per_tag=2 → 16

Tag 1 allows only two items: 7 and 6. The third pick is 3 from tag 2: 7 + 6 + 3 = 16.

Example 2

values=[4, 9, 2], tags=[5, 5, 5], max_items=3, per_tag=1 → 9

All items share one tag and only one may be taken, so we take 9.

Example 3

values=[0, 8, 1, 4], tags=[2, 3, 4, 3], max_items=2, per_tag=2 → 12

Constraints

1 ≤ n = len(values) = len(tags) ≤ 2·10⁴
0 ≤ values[i], tags[i] ≤ 2·10⁴
1 ≤ max_items, per_tag ≤ n

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Hash Table Counting Sorting

Similar problems

Jobs With a Cooldown Medium Spread Out the Labels Medium Fewest Kinds After Removals Medium Palindromes From Shared Letters Medium More Than a Third of the Votes Medium

Input

values=[7, 6, 5, 3], tags=[1, 1, 1, 2], max_items=3, per_tag=2

Expected

Run checks the first 3 tests in your browser. Submit checks all 102 tests on the server, hidden ones included.