3296. Minimum Number of Seconds to Make Mountain Height Zero

// Approach: Binary search on time; each worker with rank r decreases height h in r*h*(h+1)/2 seconds.
// Time: O(n log(min * h²)) Space: O(1)

public class Solution 
{
    public long MinNumberOfSeconds(int mountainHeight, int[] workerTimes) 
    {
        long l = 1;
        long r = (long)workerTimes.Min() * mountainHeight * (mountainHeight + 1) / 2;

        while (l < r) 
        {
            long m = (l + r) / 2;
            if (GetReducedHeight(workerTimes, m) < mountainHeight)
                l = m + 1;
            else
                r = m;
        }

        return l;
    }

    // Returns the total height reduced by all workers in `m` seconds.
    private int GetReducedHeight(int[] workerTimes, long m) 
    {
        int reducedHeight = 0;
        foreach (int workerTime in workerTimes) 
        {
            // The height `x` that a worker with working time `w` reduces in `m`
            // seconds.
            // w * (1 + 2 + ... + x) <= m
            //       (1 + x) * x / 2 <= m / w
            //   x^2 + x - 2 * m / w <= 0
            //                     x <= (-1 + sqrt(1 + 8 * m / w)) / 2
            reducedHeight += (int)((-1 + Math.Sqrt(1 + 8.0 * m / workerTime)) / 2);
        }
        
        return reducedHeight;
    }
}