A van drives one fixed route serving n trips. Trip i carries p[i] passengers who board at time b[i] and alight at time a[i], with b[i] < a[i]. Passengers of a trip occupy seats during the half-open interval [b[i], a[i]) — riders who alight at a given time free their seats before anyone boarding at that same time needs them.
Find the minimum seat capacity so that at no instant does the number of seated passengers exceed the capacity.
Line 1: an integer n.
Next n lines: three integers p, b, a — passenger count, board time, alight time.
A single integer: the minimum required seat capacity.
Example 1
Input
2 3 1 5 2 2 6
Expected
5
Explanation
During [2,5) both trips are aboard: 3 + 2 = 5 passengers, the peak. Capacity 5 is required.
Example 2
Input
2 4 1 3 5 3 7
Expected
5
Explanation
The first trip alights at time 3, exactly when the second boards, so they never overlap; peak load is max(4, 5) = 5.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →