Best Picks From Capped Shelves

Medium

A warehouse has n shelves with m items each. Item values are given in the table shelves: shelves[i][j] is the value of item j on shelf i. You may take at most total items overall, and at most caps[i] of them from shelf i. Return the largest total value you can carry away.

Example 1

shelves=[[4, 9, 2], [7, 1, 8]], caps=[1, 2], total=3 → 24

Only one item may come from the first shelf, so take 9. Two may come from the second: 8 and 7. The sum is 24.

Example 2

shelves=[[5, 6], [3, 10]], caps=[2, 2], total=2 → 16

Only two items in total: 10 from the second shelf and 6 from the first, for 16.

Example 3

shelves=[[3, 3, 3]], caps=[0], total=0 → 0

Constraints

n = len(shelves) = len(caps), m = len(shelves[i])
1 ≤ n, m ≤ 500
0 ≤ shelves[i][j] ≤ 10⁵
0 ≤ caps[i] ≤ m
0 ≤ total ≤ min(n · m, sum(caps))

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Matrix Sorting Heap (Priority Queue)

Similar problems

Spend the Most Across Shops Hard Studios for Recording Sessions Medium K-th Smallest in a Sorted Grid Medium Jobs With a Cooldown Medium Spread Out the Labels Medium

Input

shelves=[[4, 9, 2], [7, 1, 8]], caps=[1, 2], total=3

Expected

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