Determine whether a sequence of passenger trips can be completed without exceeding a car’s seat capacity at any point along the route.
Problem
You are given a car with a fixed number of seats and a list of passenger trips. Each trip describes how many passengers need to be picked up, where they start, and where they get off.
A trip is represented as [numPassengers, startLocation, endLocation], meaning:
numPassengerspassengers get in the car atstartLocation- the same passengers leave the car at
endLocation - the trip uses capacity for every location in the half-open interval
[startLocation, endLocation)
Return true if it is possible to complete all trips without ever having more passengers in the car than the seat capacity. Otherwise, return false.
Notes
- Multiple trips may overlap in distance.
- Passengers leaving at a location free up seats before passengers starting at the same location are counted for the next segment.
- You only need to determine feasibility, not the actual driving order.
Input Format
- An integer
capacity. - A list of trips
trips, where each trip is an array of three integers:[numPassengers, startLocation, endLocation].
Interpretation
Each trip occupies seats for all positions from startLocation up to, but not including, endLocation.
Output Format
- Return
trueif all trips can be served without exceedingcapacityat any point. - Otherwise, return
false.
Constraints
1 <= trips.length- Each trip contains exactly 3 integers.
1 <= numPassengers0 <= startLocation < endLocationcapacity >= 0
Locations are typically small non-negative integers in the standard formulation.
Example 1
Input
capacity = 4 trips = [[2,1,5],[3,3,7]]
Output
false
Explanation
Between locations 3 and 5, there are 2 passengers from the first trip and 3 from the second, for a total of 5, which exceeds the capacity of 4.
Example 2
Input
capacity = 5 trips = [[2,1,5],[3,5,7]]
Output
true
Explanation
The first trip ends at location 5, and the second trip starts there. Since passengers leaving at 5 free seats before new passengers at 5 are counted, the car never exceeds capacity.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.