3296. Minimum Number of Seconds to Make Mountain Height Zero

Description

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.

Example 1:

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:

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:

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⁵
1 <= workerTimes.length <= 10⁴
1 <= workerTimes[i] <= 10⁶

Solutions

Solution 1: Binary Search

We notice that if all workers can reduce the mountain height to $0$ in $t$ seconds, then for any $t' > t$, the workers can also reduce the mountain height to $0$ in $t'$ seconds. Therefore, we can use binary search to find the minimum $t$ such that the workers can reduce the mountain height to $0$ in $t$ seconds.

We define a function $\textit{check}(t)$, which indicates whether the workers can reduce the mountain height to $0$ in $t$ seconds. Specifically, we iterate through each worker. For the current worker $\textit{workerTimes}[i]$, assuming they reduce the height by $h'$ in $t$ seconds, we can derive the inequality:

$$ \left(1 + h'\right) \cdot \frac{h'}{2} \cdot \textit{workerTimes}[i] \leq t $$

Solving the inequality, we get:

$$ h' \leq \left\lfloor \sqrt{\frac{2t}{\textit{workerTimes}[i]} + \frac{1}{4}} - \frac{1}{2} \right\rfloor $$

We can sum up all the $h'$ values for the workers to get the total reduced height $h$. If $h \geq \textit{mountainHeight}$, it means the workers can reduce the mountain height to $0$ in $t$ seconds.

Next, we determine the left boundary of the binary search $l = 1$. Since there is at least one worker, and each worker's working time does not exceed $10^6$, to reduce the mountain height to $0$, it takes at least $(1 + \textit{mountainHeight}) \cdot \textit{mountainHeight} / 2 \cdot \textit{workerTimes}[i] \leq 10^{16}$ seconds. Therefore, we can set the right boundary of the binary search to $r = 10^{16}$. Then, we continuously halve the interval $[l, r]$ until $l = r$. At this point, $l$ is the answer.

The time complexity is $O(n \times \log M)$, where $n$ is the number of workers, and $M$ is the right boundary of the binary search, which is $10^{16}$ in this problem.

Python3JavaC++GoTypeScript

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
        def check(t: int) -> bool:
            h = 0
            for wt in workerTimes:
                h += int(sqrt(2 * t / wt + 1 / 4) - 1 / 2)
            return h >= mountainHeight

        return bisect_left(range(10**16), True, key=check)

class Solution {
    private int mountainHeight;
    private int[] workerTimes;

    public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
        this.mountainHeight = mountainHeight;
        this.workerTimes = workerTimes;
        long l = 1, r = (long) 1e16;
        while (l < r) {
            long mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private boolean check(long t) {
        long h = 0;
        for (int wt : workerTimes) {
            h += (long) (Math.sqrt(t * 2.0 / wt + 0.25) - 0.5);
        }
        return h >= mountainHeight;
    }
}

class Solution {
public:
    long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
        using ll = long long;
        ll l = 1, r = 1e16;
        auto check = [&](ll t) -> bool {
            ll h = 0;
            for (int& wt : workerTimes) {
                h += (long long) (sqrt(t * 2.0 / wt + 0.25) - 0.5);
            }
            return h >= mountainHeight;
        };
        while (l < r) {
            ll mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

func minNumberOfSeconds(mountainHeight int, workerTimes []int) int64 {
    return int64(sort.Search(1e16, func(t int) bool {
        var h int64
        for _, wt := range workerTimes {
            h += int64(math.Sqrt(float64(t)*2.0/float64(wt)+0.25) - 0.5)
        }
        return h >= int64(mountainHeight)
    }))
}

function minNumberOfSeconds(mountainHeight: number, workerTimes: number[]): number {
    const check = (t: bigint): boolean => {
        let h = BigInt(0);
        for (const wt of workerTimes) {
            h += BigInt(Math.floor(Math.sqrt((Number(t) * 2.0) / wt + 0.25) - 0.5));
        }
        return h >= BigInt(mountainHeight);
    };

    let l = BigInt(1);
    let r = BigInt(1e16);

    while (l < r) {
        const mid = (l + r) >> BigInt(1);
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1n;
        }
    }

    return Number(l);
}

3296. Minimum Number of Seconds to Make Mountain Height Zero

Description

Solutions

Solution 1: Binary Search

Comments