Assign Distinct Tower Heights Under Per-Tower Limits

# Assign Distinct Tower Heights Under Per-Tower Limits ### Problem You are given an integer array `maximumHeight`. Tower `i` must receive a positive integer height that is at most `maximumHeight[i]`. No two towers may receive the same height. Return the maximum possible sum of all assigned heights. If no valid assignment exists, return `-1`. Return only the sum, not an assignment. ### C++ Interface ```cpp class Solution { public: long long maximumTotalSum(vector<int>& maximumHeight); }; ``` ### Examples #### Example 1 **Input:** `maximumHeight = [6,4,4,2]` **Output:** `15` **Explanation:** Heights `[6,4,3,2]` satisfy every tower's limit and sum to `15`. The limits sum to `16`, but the two towers limited to `4` cannot both use height `4`, so at least one unit must be lost. #### Example 2 **Input:** `maximumHeight = [1,3,1]` **Output:** `-1` **Explanation:** The first and third towers must both have height `1`, which violates the distinct-height requirement. ### Constraints - `1 <= maximumHeight.size() <= 10^5` - `1 <= maximumHeight[i] <= 10^9` ### Clarifying Questions - Can a tower have height zero? No, all assigned heights must be positive integers. - Must heights increase or decrease in the original input order? No. Only each tower's own limit and global uniqueness constrain the assignment. - Is any valid sum sufficient? No, return the largest valid sum, or `-1` when assignment is impossible. ### What a Strong Answer Covers - Respect for every original tower's upper bound and the requirement that all assigned heights differ. - A proof that the returned sum is maximal, or that no positive distinct assignment exists. - Equal upper bounds, small limits that can prevent feasibility, and a single tower. - Time and space bounds for `10^5` towers, with a return type that handles the total sum. ### Follow-up Questions - How could you also return a valid maximizing assignment in the original tower order? - Can the maximum sum exceed a signed 32-bit integer under these constraints? ```hint Choose an order to compare limits Consider the towers from the largest upper bound to the smallest. Can a feasible assignment be rearranged into the same descending order without reducing its sum? ``` ```hint Track the height actually chosen After assigning a tower, later choices must remain strictly below that assigned height, not merely below its original upper bound. Detect when no positive choice remains. ```