0914MediumArrayMathBinary SearchGreedyHeap (Priority Queue)

Clearing the Spoil Heap Together

Tracked in this browser only

Trains the technique from

LeetCode 3296Minimum Number of Seconds to Make Mountain Height Zero

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_number_of_seconds(mountainHeight: int, workerTimes: list[int]) -> int:

Java

public long minNumberOfSeconds(int mountainHeight, int[] workerTimes)

The intended approach

Time O(w log T) for w diggers over a time range T, one pass over the diggers per candidate.Space O(1).

Ask the question the other way round: given a number of seconds, can the heap be cleared inside it? A digger allowed that long clears as many units as its own formula permits, which is the largest whole `x` with the rate times `x` times `x` plus one, halved, still inside the allowance, and that comes straight from solving a quadratic. Add those figures over the diggers and the allowance works exactly when the total reaches the heap's height. That test only ever becomes easier as the allowance grows, so the smallest allowance that works can be found by halving the range, starting from an upper bound taken from one digger doing the whole heap alone.

Pythonentry point: min_number_of_seconds

def min_number_of_seconds(mountainHeight, workerTimes):
    def clears(rate, seconds):
        # largest whole x with rate * x * (x + 1) / 2 <= seconds
        room = 2 * seconds // rate
        x = int((room ** 0.5))
        while x * (x + 1) > room:
            x -= 1
        while (x + 1) * (x + 2) <= room:
            x += 1
        return x

    low = 1
    slowest = 0
    for rate in workerTimes:
        if rate > slowest:
            slowest = rate
    high = slowest * mountainHeight * (mountainHeight + 1) // 2
    while low < high:
        mid = (low + high) // 2
        done = 0
        for rate in workerTimes:
            done += clears(rate, mid)
            if done >= mountainHeight:
                break
        if done >= mountainHeight:
            high = mid
        else:
            low = mid + 1
    return low

The obvious version

Hand out the units one at a time instead. Keep, for each digger, how long it would have worked once it took one more unit, and always give the next unit to whichever digger that figure is smallest for. The answer is the largest such figure reached. Works the schedule out directly and never asks whether a given allowance is enough.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_number_of_seconds(mountainHeight, workerTimes):
    import heapq
    heap = []
    for rate in workerTimes:
        heapq.heappush(heap, (rate, 1, rate))
    answer = 0
    for _ in range(mountainHeight):
        spent, taken, rate = heapq.heappop(heap)
        if spent > answer:
            answer = spent
        nxt = taken + 1
        heapq.heappush(heap, (rate * nxt * (nxt + 1) // 2, nxt, rate))
    return answer

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in