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.
Each worker may reduce the mountain's height by any non-negative integer amount. If worker i reduces the height by x, then:
- reducing the first unit of height takes
workerTimes[i]seconds, - reducing the second unit takes
workerTimes[i] * 2seconds, - ...
- reducing the
x-th unit takesworkerTimes[i] * xseconds.
The total time spent by worker i is the sum of the times required for all x units they reduce. As all workers operate simultaneously, the total time required is the maximum time spent by any worker.
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] = 2seconds. - Worker 1 reduces the height by 2, taking
workerTimes[1] + workerTimes[1] * 2 = 3seconds. - Worker 2 reduces the height by 1, taking
workerTimes[2] = 1second.
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 = 9seconds. - Worker 1 reduces the height by 3, taking
workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12seconds. - Worker 2 reduces the height by 3, taking
workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12seconds. - Worker 3 reduces the height by 2, taking
workerTimes[3] + workerTimes[3] * 2 = 12seconds.
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 <= 1051 <= workerTimes.length <= 1041 <= workerTimes[i] <= 106
Solutions
This code finds the minimum time needed to clear a mountain with multiple workers using binary search on the answer. It searches for a time value between 1 and a theoretical maximum, and for each candidate time mid, it calculates how much work each worker can accomplish: each worker gets mid / t time units (where t is their base time), and the formula (-1.0 + Math.sqrt(1 + work * 8)) / 2 converts those time units into completed levels (solving the quadratic equation from the fact that level k takes 1*t + 2*t + ... + k*t total time). If all workers combined can finish at least mountainHeight levels in time mid, the answer might be smaller, so the search narrows the upper bound; otherwise, more time is needed. The algorithm returns the smallest time where workers can collectively complete the mountain.
/**
* @param {number} mountainHeight
* @param {number[]} workerTimes
* @return {number}
*/
var minNumberOfSeconds = function (mountainHeight, workerTimes) {
const EPS = 1e-7;
const maxWorkerTimes = Math.max(...workerTimes);
let l = 1;
let r = (maxWorkerTimes * mountainHeight * (mountainHeight + 1)) / 2;
let ans = 0;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
let cnt = 0;
for (const t of workerTimes) {
const work = Math.floor(mid / t);
const k = Math.floor((-1.0 + Math.sqrt(1 + work * 8)) / 2 + EPS);
cnt += k;
}
if (cnt >= mountainHeight) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
};