One Pick per Shelf

Hard

A warehouse rack is described by shelves: shelves[i] lists the prices of the items on shelf i, all positive integers. Pick some items (at least one) so that: - at most one item is taken from each shelf; - all picked prices are pairwise different. Return the largest possible sum of the picked prices.

Example 1

shelves=[[3, 7, 2], [7, 1, 4], [2, 2, 9]] → 20

Take 7 from the first shelf, 4 from the second (7 is already taken) and 9 from the third: 7 + 4 + 9 = 20.

Example 2

shelves=[[5, 5], [5, 5]] → 5

Every shelf holds only 5s and a number cannot repeat, so only one item is taken: the answer is 5.

Constraints

1 ≤ len(shelves) ≤ 10
1 ≤ len(shelves[i]) ≤ 10
1 ≤ shelves[i][j] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Dynamic Programming Bitmask Matrix

Similar problems

Exam Seating Without Peeking Hard Wire Two Panels Hard Settle Up in the Fewest Transfers Hard Two Groups With the Same Average Hard Assembling Fragments Hard

Input

shelves=[[3, 7, 2], [7, 1, 4], [2, 2, 9]]

Expected

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