Show problems as
Classic problem #3296MediumArrayMathBinary SearchGreedyHeap (Priority Queue)

Minimum Number of Seconds to Make Mountain Height Zero

Real-world version: Clearing the Spoil Heap Together
Tracked in this browser only
Read Minimum Number of Seconds to Make Mountain Height Zero on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A spoil heap holds mountainHeight units. Digger i works at a rate given by workerTimes[i]: clearing x units takes that digger workerTimes[i] * x * (x + 1) / 2 seconds in total.

Every digger works at the same time as the others, and between them they must clear the whole heap. Return the fewest seconds until the heap is gone, which is the longest any one digger has to work.

Examples

Example 1

Input
mountainHeight = 10, workerTimes = [2, 2]
Output
30

Splitting the ten units five apiece has each digger spend 2 times 15, which is 30 seconds, and no other split of the heap finishes sooner.

Example 2

Input
mountainHeight = 10, workerTimes = [4]
Output
220

The single digger must clear all ten units, which costs 4 times 55.

Example 3

Input
mountainHeight = 3, workerTimes = [1, 1000000]
Output
6

The slow digger is worth one unit at most: taking one costs it a million seconds, while the fast digger clearing all three costs only six. Leaving it idle is better, so the answer is the fast digger's six seconds.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_number_of_seconds(mountainHeight: int, workerTimes: list[int]) -> int:
Java
public long minNumberOfSeconds(int mountainHeight, int[] workerTimes)

More on the same topics