Minimum Number of Seconds to Make Mountain Height Zero
Problem
A mountain has height mountainHeight. Worker i has base time workerTimes[i]: its 1st unit costs workerTimes[i] seconds, its 2nd unit workerTimes[i]·2, …, its x-th unit workerTimes[i]·x. So reducing x units costs workerTimes[i]·x·(x+1)/2. All workers act at once, so total time is the maximum worker time. Return the minimum seconds to bring the height to 0.
mountainHeight = 4, workerTimes = [2,1,1]3def minNumberOfSeconds(mountainHeight, workerTimes):
# units a worker (base t) can do within budget T: t*x*(x+1)/2 <= T
def units(t, T):
cap = T // t # need x*(x+1)/2 <= cap
x = (isqrt(1 + 8 * cap) - 1) // 2 # closed-form, then nudge
while (x + 1) * (x + 2) // 2 <= cap:
x += 1
return x
def feasible(T): # can all workers clear H in T?
total = 0
for t in workerTimes:
total += units(t, T)
if total >= mountainHeight:
return True
return False
lo, hi = 1, min(workerTimes) * mountainHeight * (mountainHeight + 1) // 2
while lo < hi: # smallest feasible T
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return lofunction minNumberOfSeconds(mountainHeight, workerTimes) {
// units a worker (base t) can do within budget T: t*x*(x+1)/2 <= T
const units = (t, T) => {
const cap = Math.floor(T / t); // need x*(x+1)/2 <= cap
let x = Math.floor((Math.sqrt(1 + 8 * cap) - 1) / 2);
while ((x + 1) * (x + 2) / 2 <= cap) x++;
return x;
};
const feasible = (T) => { // can all workers clear H in T?
let total = 0;
for (const t of workerTimes) {
total += units(t, T);
if (total >= mountainHeight) return true;
}
return false;
};
let lo = 1;
let hi = Math.min(...workerTimes) * mountainHeight * (mountainHeight + 1) / 2;
while (lo < hi) { // smallest feasible T
const mid = Math.floor((lo + hi) / 2);
if (feasible(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
long lo = 1, hi = 0, minT = Integer.MAX_VALUE;
for (int t : workerTimes) minT = Math.min(minT, t);
hi = minT * (long) mountainHeight * (mountainHeight + 1) / 2;
while (lo < hi) { // smallest feasible T
long mid = (lo + hi) / 2;
if (feasible(mid, mountainHeight, workerTimes)) hi = mid;
else lo = mid + 1;
}
return lo;
}
boolean feasible(long T, int H, int[] workerTimes) {
long total = 0;
for (int t : workerTimes) {
long cap = T / t; // need x*(x+1)/2 <= cap
long x = (long) ((Math.sqrt(1 + 8.0 * cap) - 1) / 2);
while ((x + 1) * (x + 2) / 2 <= cap) x++;
total += x;
if (total >= H) return true;
}
return false;
}long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) {
auto units = [](long long t, long long T) {
long long cap = T / t; // need x*(x+1)/2 <= cap
long long x = (long long)((sqrt(1 + 8.0 * cap) - 1) / 2);
while ((x + 1) * (x + 2) / 2 <= cap) x++;
return x;
};
auto feasible = [&](long long T) { // can all workers clear H?
long long total = 0;
for (int t : workerTimes) {
total += units(t, T);
if (total >= mountainHeight) return true;
}
return false;
};
long long mn = *min_element(workerTimes.begin(), workerTimes.end());
long long lo = 1, hi = mn * (long long) mountainHeight * (mountainHeight + 1) / 2;
while (lo < hi) { // smallest feasible T
long long mid = (lo + hi) / 2;
if (feasible(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}Explanation
The cost for one worker to chip away x units is the triangular sum t·(1 + 2 + … + x) = t·x·(x+1)/2. Because workers run in parallel, the time the whole crew needs is the maximum single-worker time, and we want to choose how much each does so that the most-burdened worker finishes as early as possible.
The key observation is monotonicity: if a budget of T seconds is enough to flatten the mountain, then any larger budget is also enough. That lets us binary search on T — the answer — instead of guessing assignments.
For a fixed budget T, each worker independently does as many units as it can afford: the most units x with t·x·(x+1)/2 ≤ T, i.e. x·(x+1)/2 ≤ ⌊T/t⌋. We solve that with the quadratic closed form x = ⌊(√(1+8·cap) − 1)/2⌋ and nudge up once to absorb any floating-point rounding. Summing each worker's units gives the total height the crew can remove in T seconds.
If that total reaches mountainHeight, the budget is feasible; we shrink the upper bound. Otherwise we raise the lower bound. We seed hi with the time a single (fastest) worker would need to do the whole mountain alone — always enough — and search down to the true minimum.
Example: mountainHeight = 4, workerTimes = [2,1,1]. At T = 3 the workers can do 1, 2, 1 units = 4 ≥ 4, so 3 is feasible; at T = 2 they manage 1, 1, 1 = 3 < 4, infeasible. The smallest feasible budget is 3.