Problem

You are given an integer mountainHeight denoting the height of a mountain.

You are also given an integer array workerTimes representing the work time of workers in seconds.

The workers work simultaneously to reduce the height of the mountain. For worker i:

  • To decrease the mountain’s height by x, it takes workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x seconds. For example:
  • To reduce the height of the mountain by 1, it takes workerTimes[i] seconds.
  • To reduce the height of the mountain by 2, it takes workerTimes[i] + workerTimes[i] * 2 seconds, and so on.

Return an integer representing the minimum number of seconds required for the workers to make the height of the mountain 0.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


Input: mountainHeight = 4, workerTimes = [2,1,1]

Output: 3

Explanation:

One way the height of the mountain can be reduced to 0 is:

  * Worker 0 reduces the height by 1, taking `workerTimes[0] = 2` seconds.
  * Worker 1 reduces the height by 2, taking `workerTimes[1] + workerTimes[1] * 2 = 3` seconds.
  * Worker 2 reduces the height by 1, taking `workerTimes[2] = 1` second.

Since they work simultaneously, the minimum time needed is `max(2, 3, 1) = 3`
seconds.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


Input: mountainHeight = 10, workerTimes = [3,2,2,4]

Output: 12

Explanation:

  * Worker 0 reduces the height by 2, taking `workerTimes[0] + workerTimes[0] * 2 = 9` seconds.
  * Worker 1 reduces the height by 3, taking `workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12` seconds.
  * Worker 2 reduces the height by 3, taking `workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12` seconds.
  * Worker 3 reduces the height by 2, taking `workerTimes[3] + workerTimes[3] * 2 = 12` seconds.

The number of seconds needed is `max(9, 12, 12, 12) = 12` seconds.

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: mountainHeight = 5, workerTimes = [1]

Output: 15

Explanation:

There is only one worker in this example, so the answer is `workerTimes[0] +
workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0]
* 5 = 15`.

Constraints

  • 1 <= mountainHeight <= 10^5
  • 1 <= workerTimes.length <= 10^4
  • 1 <= workerTimes[i] <= 10^6

Solution

Method 1 – Greedy + Binary Search (Partitioning)

Intuition

Each worker can reduce some part of the mountain, and the time for each is the sum of an arithmetic progression. We want to partition the mountainHeight among workers so that the maximum time among all workers is minimized. This is a classic load balancing problem solved by binary search.

Approach

  1. Use binary search for the answer: the minimum possible max time.
  2. For each candidate time, check if it’s possible to partition the mountainHeight among workers so that no worker exceeds the time.
  3. For each worker, compute the max height they can reduce in the given time.
  4. Sum up all max heights; if >= mountainHeight, it’s feasible.
  5. Return the minimum feasible time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int minSeconds(int mountainHeight, vector<int>& workerTimes) {
        int left = 1, right = 1e15, ans = right;
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            long long total = 0;
            for (int wt : workerTimes) {
                long long l = 0, r = mountainHeight;
                while (l < r) {
                    long long m = (l + r + 1) / 2;
                    long long t = wt * m * (m + 1) / 2;
                    if (t <= mid) l = m;
                    else r = m - 1;
                }
                total += l;
            }
            if (total >= mountainHeight) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func minSeconds(mountainHeight int, workerTimes []int) int64 {
    left, right := int64(1), int64(1e15)
    ans := right
    for left <= right {
        mid := (left + right) / 2
        total := int64(0)
        for _, wt := range workerTimes {
            l, r := int64(0), int64(mountainHeight)
            for l < r {
                m := (l + r + 1) / 2
                t := int64(wt) * m * (m + 1) / 2
                if t <= mid {
                    l = m
                } else {
                    r = m - 1
                }
            }
            total += l
        }
        if total >= int64(mountainHeight) {
            ans = mid
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public long minSeconds(int mountainHeight, int[] workerTimes) {
        long left = 1, right = (long)1e15, ans = right;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long total = 0;
            for (int wt : workerTimes) {
                long l = 0, r = mountainHeight;
                while (l < r) {
                    long m = (l + r + 1) / 2;
                    long t = wt * m * (m + 1) / 2;
                    if (t <= mid) l = m;
                    else r = m - 1;
                }
                total += l;
            }
            if (total >= mountainHeight) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun minSeconds(mountainHeight: Int, workerTimes: IntArray): Long {
        var left = 1L; var right = 1_000_000_000_000_000L; var ans = right
        while (left <= right) {
            val mid = (left + right) / 2
            var total = 0L
            for (wt in workerTimes) {
                var l = 0L; var r = mountainHeight.toLong()
                while (l < r) {
                    val m = (l + r + 1) / 2
                    val t = wt * m * (m + 1) / 2
                    if (t <= mid) l = m else r = m - 1
                }
                total += l
            }
            if (total >= mountainHeight) {
                ans = mid
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def minSeconds(self, mountainHeight: int, workerTimes: list[int]) -> int:
        left, right = 1, 10**15
        ans = right
        while left <= right:
            mid = (left + right) // 2
            total = 0
            for wt in workerTimes:
                l, r = 0, mountainHeight
                while l < r:
                    m = (l + r + 1) // 2
                    t = wt * m * (m + 1) // 2
                    if t <= mid:
                        l = m
                    else:
                        r = m - 1
                total += l
            if total >= mountainHeight:
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn min_seconds(mountain_height: i32, worker_times: Vec<i32>) -> i64 {
        let (mut left, mut right) = (1i64, 1e15 as i64);
        let mut ans = right;
        while left <= right {
            let mid = (left + right) / 2;
            let mut total = 0i64;
            for &wt in &worker_times {
                let (mut l, mut r) = (0i64, mountain_height as i64);
                while l < r {
                    let m = (l + r + 1) / 2;
                    let t = wt as i64 * m * (m + 1) / 2;
                    if t <= mid { l = m; } else { r = m - 1; }
                }
                total += l;
            }
            if total >= mountain_height as i64 {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    minSeconds(mountainHeight: number, workerTimes: number[]): number {
        let left = 1, right = 1e15, ans = right;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            let total = 0;
            for (const wt of workerTimes) {
                let l = 0, r = mountainHeight;
                while (l < r) {
                    let m = Math.floor((l + r + 1) / 2);
                    let t = wt * m * (m + 1) / 2;
                    if (t <= mid) l = m;
                    else r = m - 1;
                }
                total += l;
            }
            if (total >= mountainHeight) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(W * log(H) * log(T)) — W = number of workers, H = mountainHeight, T = max seconds.
  • 🧺 Space complexity: O(1) — constant extra space.