A shuttle serves n passenger trips along one route. Trip i boards riders passengers at position board who leave at position alight, occupying the shuttle over the half-open stretch [board, alight) (a passenger leaving at position x is not aboard at x). Report the minimum seat capacity the shuttle must have so that it never runs out of seats at any point of the route.
Line 1: an integer n.
Next n lines: three integers board alight riders (with board < alight).
A single integer: the peak number of passengers aboard at once, i.e. the minimum required capacity.
Example 1
Input
3 0 4 2 1 3 3 2 5 1
Expected
6
Explanation
At position 2 all three trips overlap, carrying 2 + 3 + 1 = 6 passengers, which is the peak, so the shuttle needs 6 seats.
Example 2
Input
2 0 2 5 2 4 5
Expected
5
Explanation
The two trips only touch at position 2, so at most 5 passengers ride at once: capacity 5 suffices.
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 →