All crates on a loading dock must go into one vertical column. Crate i is described by
crates[i] = (weight, tolerance). Once the column is built, the strain on a crate is
(total weight of all crates above it) - (its tolerance)
so the top crate has strain -tolerance. Strains may be negative. You may choose any order
for the column. Return the smallest possible value of the largest strain in the column.
Return 0 if there are no crates.
Examples
Input: crates = [(3, 1), (2, 5), (4, 2)]
Output: 2
Explanation: top to bottom (3, 1), (4, 2), (2, 5) gives strains -1, 1 and 7 - 5 = 2.
No order does better.
Input: crates = [(10, 0)]
Output: 0
Constraints
0 <= len(crates) <= 10**51 <= weight <= 10**4,0 <= tolerance <= 10**9- An O(n log n) solution is expected; trying orders, or re-adding the weights above every crate, is too slow.
Goals
- Find the right sort key with an exchange argument on two neighbouring crates
- Compute every strain in one pass with a running sum
- Handle negative strains and an empty list