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 <= 105
• 1 <= workerTimes.length <= 104
• 1 <= workerTimes[i] <= 106

 

Solutions

Solution: Binary Search

• Time complexity: O(nlogMH²)
  • M = max workerTimes
  • H = mountainHeight
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} mountainHeight
 * @param {number[]} workerTimes
 * @return {number}
 */
const minNumberOfSeconds = function (mountainHeight, workerTimes) {
  const maxWorkerTime = Math.max(...workerTimes);
  let left = 1;
  let right = (maxWorkerTime * (1 + mountainHeight) * mountainHeight) / 2;
  let result = 0;

  const isCompleted = seconds => {
    let reduceHeight = 0;

    for (const time of workerTimes) {
      // 一元二次方程求根公式
      const work = Math.floor(seconds / time);
      const height = Math.floor((-1 + Math.sqrt(1 + 8 * work)) / 2);

      reduceHeight += height;

      if (reduceHeight >= mountainHeight) return true;
    }

    return false;
  };

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (isCompleted(mid)) {
      right = mid - 1;
      result = mid;
    } else {
      left = mid + 1;
    }
  }

  return result;
};