A farm has one grazing field that only one cow can use at a time. Cow i shows up at time arrival_i and, once she gets the field, grazes for duration_i time units. Cows are listed in order of seniority: index 0 is the most senior.
The rules:
- When the field is free and cows are waiting, the most senior waiting cow (smallest index) goes in immediately.
- When the field is free and nobody is waiting, the field sits empty until the next cow arrives. If several cows arrive at that same moment, the most senior of them goes first.
- A cow that arrives at exactly the moment the field frees up counts as waiting at that moment.
- A cow's wait is the time she starts grazing minus her arrival time.
Write max_wait(cows) where cows is a list of (arrival, duration) pairs in seniority order, and return the longest wait any cow experiences.
max_wait([(10, 5), (3, 8), (4, 2), (12, 1)]) # 12
max_wait([(0, 4)]) # 0
max_wait([(5, 1), (0, 10), (0, 1)]) # 11
Trace of the first example: cow 1 arrives first and grazes 3..11. At 11, cows 0 (arrived 10) and 2 (arrived 4) are waiting; cow 0 is more senior, so she grazes 11..16. At 16, cows 2 and 3 are waiting; cow 2 grazes 16..18 (wait 12) and cow 3 grazes 18..19 (wait 6). Seniority beats arrival time, which is why cow 2 waits so long.
Constraints: up to 100,000 cows, times and durations up to 10^9. Aim for O(n log n): scanning all waiting cows each time the field frees is O(n²) and too slow.
Show hint
Simulate the field in time order. Cows join the waiting group as their arrival time passes; the group only ever needs to hand over its most senior member quickly.