757. Crews That Must Set Up First

A wall is divided into L identical panels. k crews are available. Crew i spends s[i] minutes setting up its equipment before it can touch the wall at all, and then finishes one panel every t[i] minutes. All the crews set up and work at the same time, and a panel is done by one crew alone.

Print the fewest whole minutes after which the wall is finished.

setups 0 0 0, rates 1 2 3, L = 10 -> 6 setups 4 0, rates 1 3, L = 5 -> 7 setups 10 10 10, rates 1 1 1, L = 6 -> 12 setups 10 10 10, rates 1 1 1, L = 7 -> 13

In the first example, by minute 6 the crews have finished 6, 3 and 2 panels, which is 11, enough for the wall. By minute 5 they have 5, 2 and 1, which is 8.

## What a candidate minute buys

By minute T, crew i has finished

0 if T < s[i] (T - s[i]) / t[i] otherwise, rounded down

panels. Add that across the crews and compare with L.

## Why the predicate is monotone

Each crew's count is non-decreasing in T: before its setup ends it is stuck at zero, and after that it is a floor division whose numerator grows with T. A sum of non-decreasing terms is non-decreasing, so the minutes at which the wall is finished form a suffix, which is what lets binary search find the first one.

## The bounds

lo = 0. Nothing is done at minute zero unless the wall has no panels, and it always has at least one, but starting there costs one iteration and removes a special case.

hi = min over i of (s[i] + t[i] * L). That is the minute by which the single best crew, chosen after looking at the setup cost as well as the rate, would have finished the whole wall alone. It is therefore certainly enough for all of them together.

The tempting hi = max(t) * L is WRONG, because it ignores the setup entirely: with setups of 10 and a rate of 1 per panel on a 6 panel wall, that bound gives 6 while the answer is 12.

## The boundary that breaks a careless implementation

The crew that has not finished setting up.

(T - s[i]) / t[i] with T < s[i] is a division of a NEGATIVE number. C, C++, Java and JavaScript truncate it toward zero and Python floors it downward, so the term comes out as zero, or as a negative count that quietly SUBTRACTS panels from the total. Either way the check is wrong, and it is wrong only on candidates below some crew's setup time, which is exactly the region the early iterations of the search visit. Guard it with an explicit if (T >= s[i]).

The second boundary is the usual one: stop adding once the running count reaches L. That is a speed fix rather than an overflow fix, and the two frightening numbers cannot meet. A crew with t = 1 pulls hi down to s + L, at most 2 * 10^6, so a one-minute crew and a candidate near 10^12 never occur in the same input. More generally T never exceeds s[i] + t[i] * L for ANY crew i, so (T - s[i]) / t[i] <= L for every crew and the untrimmed total is at most k * L = 10^5 * 10^6 = 10^11. That is a 64-bit value but a long way below the ceiling. What the early exit saves is 10^5 divisions on each step of a search the first few crews have already decided.

## Overflow

hi is s + t * L, up to 10^6 + 10^6 * 10^6, just over 10^12. That is a 64-bit value in C, C++ and Java, and it is the mid-point of the search as well, so every variable in the check has to be wide.

## Related problems

Problem 753 is this problem with every setup equal to zero, and comparing the two bounds is the point of the pair. Problem 758 keeps the setups out but lets the rate decay as a crew works.

## Cost

Time O(k log(min(s + t * L))). Space O(k).

Constraints - `1 ≤ k ≤ 100000` - `1 ≤ L ≤ 10^6` - `0 ≤ s[i] ≤ 10^6` - `1 ≤ t[i] ≤ 10^6`