Minimum Number of Seconds to Make Mountain Height Zero
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
3One optimal assignment has workers reduce 1, 2, and 1 units respectively, taking max(2, 3, 1) = 3 seconds.
Example 2
Input
mountainHeight = 10, workerTimes = [3,2,2,4]Output
12Workers can reduce 2, 3, 3, and 2 units respectively, taking max(9, 12, 12, 12) = 12 seconds.
Constraints
- 1 <= mountainHeight <= 10^5
- 1 <= workerTimes.length <= 10^4
- 1 <= workerTimes[i] <= 10^6