Maximize the Total Height of Unique Towers

Problem Description

You are given an array maximumHeight, where maximumHeight[i] denotes the maximum height the ith tower can be assigned. Your task is to assign a height to each tower so that:

1. The height of the ith tower is a positive integer and does not exceed maximumHeight[i].
2. No two towers have the same height.

Return the maximum possible total sum of the tower heights. If it's not possible to assign heights, return -1.

Key Insights

• We need to ensure that heights assigned to towers are unique.
• The maximum height for each tower is constrained by the maximumHeight array.
• A greedy approach can be utilized by sorting the maximum heights and assigning the highest available unique heights to maximize the total sum.
• If at any point we cannot assign a unique height, we should return -1.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(1) - in-place assignment of heights without additional data structures.

Solution

To solve this problem, follow these steps:

1. Sort the maximumHeight array in descending order.
2. Initialize a variable to keep track of the last assigned height, starting from a large number.
3. Iterate through the sorted maximumHeight array and for each tower:
   • Assign the maximum possible height that is less than or equal to maximumHeight[i] and also greater than the last assigned height.
   • Update the last assigned height accordingly.
4. If at any tower we cannot assign a height, return -1.
5. Otherwise, keep a cumulative sum of the heights assigned and return it at the end.

Code Solutions