Skip to content

3301. Maximize the Total Height of Unique Towers

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.

 

Example 1:

Input: maximumHeight = [2,3,4,3]

Output: 10

Explanation:

We can assign heights in the following way: [1, 2, 4, 3].

Example 2:

Input: maximumHeight = [15,10]

Output: 25

Explanation:

We can assign heights in the following way: [15, 10].

Example 3:

Input: maximumHeight = [2,2,1]

Output: -1

Explanation:

It's impossible to assign positive heights to each index so that no two towers have the same height.

 

Constraints:

  • 1 <= maximumHeight.length <= 105
  • 1 <= maximumHeight[i] <= 109

Solutions

Solution 1: Sorting + Greedy

Thinking

Heights must be pairwise distinct and within each tower's cap. With \(n \le 10^5\), enumerating assignments is infeasible. Filling short towers first can steal large integers that tall towers still need.

To maximize the sum we should assign larger heights to towers with larger caps. After sorting \(\textit{maximumHeight}\) descending, \(mx\) stores the last assigned height.

The current tower takes \(\min(x, mx-1)\): it stays within its cap and strictly below the previous height. A non-positive value means no valid assignment exists.

We can sort the maximum heights of the towers in descending order, then allocate the heights one by one starting from the maximum height. Use a variable \(mx\) to record the current maximum allocated height.

If the current height \(x\) is greater than \(mx - 1\), update \(x\) to \(mx - 1\). If \(x\) is less than or equal to \(0\), it means the height cannot be allocated, and we directly return \(-1\). Otherwise, we add \(x\) to the answer and update \(mx\) to \(x\).

Finally, return the answer.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of the array \(\textit{maximumHeight}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maximumTotalSum(self, maximumHeight: List[int]) -> int:
        maximumHeight.sort()
        ans, mx = 0, inf
        for x in maximumHeight[::-1]:
            x = min(x, mx - 1)
            if x <= 0:
                return -1
            ans += x
            mx = x
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public long maximumTotalSum(int[] maximumHeight) {
        long ans = 0;
        int mx = 1 << 30;
        Arrays.sort(maximumHeight);
        for (int i = maximumHeight.length - 1; i >= 0; --i) {
            int x = Math.min(maximumHeight[i], mx - 1);
            if (x <= 0) {
                return -1;
            }
            ans += x;
            mx = x;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    long long maximumTotalSum(vector<int>& maximumHeight) {
        ranges::sort(maximumHeight, greater<int>());
        long long ans = 0;
        int mx = 1 << 30;
        for (int x : maximumHeight) {
            x = min(x, mx - 1);
            if (x <= 0) {
                return -1;
            }
            ans += x;
            mx = x;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func maximumTotalSum(maximumHeight []int) int64 {
    slices.SortFunc(maximumHeight, func(a, b int) int { return b - a })
    ans := int64(0)
    mx := 1 << 30
    for _, x := range maximumHeight {
        x = min(x, mx-1)
        if x <= 0 {
            return -1
        }
        ans += int64(x)
        mx = x
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function maximumTotalSum(maximumHeight: number[]): number {
    maximumHeight.sort((a, b) => a - b).reverse();
    let ans: number = 0;
    let mx: number = Infinity;
    for (let x of maximumHeight) {
        x = Math.min(x, mx - 1);
        if (x <= 0) {
            return -1;
        }
        ans += x;
        mx = x;
    }
    return ans;
}

Comments