598. Car Pooling
A shuttle with capacity seats drives east along a straight road and never turns around. You are given trips, a list where each entry trips[i] = [passengers, start, end] describes a group of passengers riders who board at kilometer marker start and get off at marker end (with start < end). A group leaving at some marker frees its seats before any group boarding at that same marker climbs in.
Your function receives the list trips and the integer capacity, and returns true if the shuttle can serve every trip without ever carrying more than capacity riders at once, or false if at some stretch of road it would be over capacity.
Example 1:
Input: trips = [[2, 1, 5], [3, 3, 7]], capacity = 4
Output: false
Explanation: Between markers 3 and 5 both groups are on board: 2 + 3 = 5 riders, but only 4 seats exist.
Example 2:
Input: trips = [[2, 1, 5], [3, 3, 7]], capacity = 5
Output: true
Explanation: The same overlap holds 5 riders, and 5 seats are available, so every trip fits.
Constraints:
- 1 ≤ trips.length ≤ 1000
- trips[i].length == 3
- 1 ≤ passengers ≤ 100
- 0 ≤ start < end ≤ 1000
- 1 ≤ capacity ≤ 10⁵
Hints:
The road only has kilometer markers 0 through 1000. Could you count, for every marker, how many riders are on board while the shuttle passes it?
You never need to know *which* riders are aboard — only the running total. Boarding at `start` is a +passengers event and leaving at `end` is a −passengers event.
Record +p at index start and −p at index end in a difference array; one prefix-sum sweep then reconstructs the exact load at every marker in O(n + 1001).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: trips = [[2, 1, 5], [3, 3, 7]], capacity = 4
Expected output: false