#206MediumPrefix Sums & Difference Arrays· Difference Array Along a Route
Shuttle Seat Capacity
Input format
`trips`: a list of `[riders, pickup, dropoff]` triples. `capacity`: the number of seats.
Output format
true if every booking can be carried, otherwise false.
Examples
Input: trips = [[2, 1, 5], [3, 3, 7]], capacity = 4
Output: false
Between stops 3 and 5 both groups are aboard: 2 + 3 = 5 riders, more than 4 seats, so the answer is false.
Input: trips = [[2, 1, 5], [3, 3, 7]], capacity = 5
Output: true
The most riders ever aboard is 5, which fits exactly, so the answer is true.
Input: trips = [[3, 0, 4], [3, 4, 8]], capacity = 3
Output: true
The first group leaves at stop 4 before the second boards there, so there are never more than 3 riders.
Constraints
- 1 <= trips.length <= 10^4
- 1 <= riders <= 100
- 0 <= pickup < dropoff <= 10^5
- 1 <= capacity <= 10^5
- #difference-array
- #prefix-sums
- #sweep-line
- #scheduling