Minimum Number of Seconds to Make Mountain Height Zero - Video Solutions

Problem Overview: You are given a mountain of height H and multiple workers. The j-th unit removed by worker i takes time[i] * j seconds, so the total time for k units becomes time[i] * (k * (k + 1) / 2). The goal is to determine the minimum number of seconds required for all workers combined to reduce the mountain height to zero.

Approach 1: Greedy Simulation with Heap (Priority Queue) (Time: O(H log n), Space: O(n))

Simulate the process of assigning work units to workers in chronological order. Each worker’s next completion time follows an arithmetic pattern: t, 3t, 6t, ... because every additional unit costs j * t seconds. Use a min-heap to track the next available completion event across all workers. Pop the earliest event, assign one unit of work, then push the worker back with the updated completion time. Repeat until H units are removed. This greedy strategy always processes the earliest finishing task first, which mirrors how the real timeline progresses. Useful for understanding the process but becomes slow when H is large.

Approach 2: Binary Search on Time (Optimal) (Time: O(n log T), Space: O(1))

Instead of simulating every unit removal, search for the smallest time T such that workers can remove at least H units in that time. For each worker with base time t, solve the inequality t * (k * (k + 1) / 2) ≤ T to determine the maximum units k they can remove. This comes from the triangular sum of increasing work costs. Rearranging gives a quadratic equation that can be solved using math or binary search per worker. Sum all workers' contributions and check if the total reaches H. Because feasibility is monotonic with respect to time, binary search efficiently finds the minimum valid T.

This approach combines mathematical reasoning with monotonic search. Each feasibility check iterates through workers and computes their maximum removable units in constant time.

Approach 3: Dynamic Programming (Time: O(n * H), Space: O(H))

Dynamic programming can model the problem as distributing H units among workers while minimizing total time. Let dp[h] represent the minimum time needed to remove h units. For each worker, iterate possible units they could remove and update the DP state using the triangular time cost t * (k * (k + 1) / 2). While this approach clearly models the incremental cost structure, its complexity grows quickly with large heights. It is mainly useful for understanding the cost relationship rather than as a production solution.

Recommended for interviews: The binary search approach is what interviewers typically expect. A brute-force or heap simulation shows you understand the timeline of work distribution, but recognizing the monotonic property and converting the worker cost into a mathematical constraint demonstrates stronger algorithmic insight. Mentioning the greedy simulation or heap idea before optimizing to binary search often earns extra credit in interviews.