Distinct Tower Heights

Medium

You need to build towers, one for each element of the array limits: the height of tower i is a positive integer no greater than limits[i]. No two towers may have the same height. Return the largest possible total height of all towers. If heights cannot be assigned under these rules, return -1.

Example 1

limits=[4, 6, 4, 2] → 15

Heights 4, 6, 3, 2 are all different and within their limits, summing to 15. The two towers capped at 4 cannot both be 4 tall.

Example 2

limits=[3, 1, 1] → -1

Both towers capped at 1 would need height 1, so distinct heights are impossible and the answer is -1.

Constraints

1 ≤ len(limits) ≤ 10⁵
1 ≤ limits[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting

Similar problems

Biggest Number From Pieces Medium Studios for Recording Sessions Medium Low, High, Low Medium Strictly Low, High, Low Medium Fewest Meetings to Cancel Medium

Input

limits=[4, 6, 4, 2]

Expected

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