An airport shuttle drives along a single road in one direction only, and positions on the road are measured in metres from the depot. It has seats seats. Group i is groups[i] = [people, board, alight]: people passengers get on at position board and get off at position alight, further along the road.
At any position, everyone getting off leaves before anyone new gets on, so a group alighting at x never shares the shuttle with a group boarding at x.
Write can_carry(groups: list[list[int]], seats: int) -> bool that returns True if the shuttle can take every group without ever having more than seats passengers on board, and False otherwise.
can_carry([[3, 2, 6], [2, 4, 9], [1, 6, 8]], 5) # True (at most 5 on board, between 4 and 6)
can_carry([[3, 2, 6], [2, 4, 9], [1, 6, 8]], 4) # False
can_carry([[4, 0, 3], [4, 3, 5]], 4) # True (the first group leaves at 3 as the second boards)
can_carry([[7, 1, 2]], 6) # False (one group alone is too big)
Constraints:
1 <= len(groups) <= 10^5.1 <= people <= 1000and0 <= board < alight <= 10^9.1 <= seats <= 10^9.
Positions go up to 10^9, so you can't keep a counter for every metre of road. Adding up the load at each boarding point from every group is O(n²). Aim for O(n log n).
Show hint
the load only changes at positions where some group boards or alights. Turn each group into two changes, handle them in road order (with drop-offs first on a tie), and keep a running total.