Car Pooling
Medium · intervals
A minibus drives along a straight road in one direction only, from small positions to large ones, and never turns back. It has capacity empty seats when it sets off.
Each trip trips[i] = [passengers, pickup, dropoff] is a group of passengers people who get on at position pickup and get off at position dropoff. At any position, the people getting off leave before the people getting on climb in.
Return true if the minibus can carry every group without ever having more people on board than capacity, and false otherwise.
Examples
Example 1
Input: trips = [[2, 1, 5], [3, 3, 7]], capacity = 4
Output: false
Between positions 3 and 5 both groups are on board, which makes 5 people for 4 seats.
Example 2
Input: trips = [[2, 1, 5], [3, 3, 7]], capacity = 5
Output: true
The most people on board at once is 5, which just fits.
Example 3
Input: trips = [[3, 2, 5], [4, 5, 8]], capacity = 4
Output: true
The first group gets off at 5 before the second group gets on, so there are never more than 4 people.
Constraints
- 1 <= len(trips) <= 10^4
- trips[i] has exactly three numbers: passengers, pickup, dropoff
- 1 <= passengers <= 1000
- 0 <= pickup < dropoff <= 10^9
- 1 <= capacity <= 10^9