Car Pooling
MediumIntervals · Amazon
A car has capacity empty seats and drives in one direction only (east) along a road marked in kilometers. It cannot turn around.
You are given trips, where trips[i] = [passengers, start, end] means a group of passengers people must be picked up at kilometer start and dropped off at kilometer end (with start < end). The group occupies seats for the stretch from start up to end.
At any kilometer, everyone who is getting off there leaves before anyone gets on. So a group dropped off at km 5 never conflicts with a group picked up at km 5.
Return True if every trip can be completed without the number of people in the car ever exceeding capacity, and False otherwise. The trips are not given in any particular order.
Example 1
- Input:
- trips = [[3, 2, 7], [4, 4, 9], [2, 7, 10]], capacity = 7
- Output:
- True
- Explanation
- Between km 4 and 7 the car carries 3 + 4 = 7 passengers, exactly the capacity. At km 7 the first group gets off before the third group of 2 gets on, so the load is 4 + 2 = 6.
Example 2
- Input:
- trips = [[1, 0, 100], [2, 50, 60]], capacity = 2
- Output:
- False
- Explanation
- The first passenger rides the whole way, so between km 50 and 60 there are 1 + 2 = 3 passengers, more than 2 seats.
Example 3
- Input:
- trips = [[2, 1, 6], [2, 3, 8], [2, 5, 9]], capacity = 5
- Output:
- False
- Explanation
- Between km 5 and 6 all three groups are in the car at once, for 6 passengers.
Constraints
1 <= trips.length <= 1000trips[i].length == 31 <= passengers <= 1000 <= start < end <= 10001 <= capacity <= 10^5