100. Carpool Capacity
A shuttle van has capacity passenger seats and drives along a straight road. Each entry of trips is [p, a, b]: a group of p passengers wants to ride between road positions a and b. They board at the smaller of the two positions and leave at the larger one; the endpoints may be listed in either order. A group is on board for positions from its boarding point up to, but not including, its exit point, so a group leaving at a position frees its seats before another group boarding there arrives. A trip with a == b never occupies a seat.
Return true if the van can serve every trip without ever carrying more than capacity passengers, otherwise false.
Example 1
- Input:
- trips = [[2,1,5],[3,3,7]], capacity = 4
- Output:
- false
- Explanation:
Between positions 3 and 5 both groups ride together, which is 5 passengers and exceeds 4, so the answer is false.
Example 2
- Input:
- trips = [[2,1,5],[3,5,8]], capacity = 3
- Output:
- true
- Explanation:
The first group leaves at 5 exactly when the second boards, so at most 3 passengers are on board and the answer is true.
Constraints
- 1 ≤ trips.length ≤ 100000
- trips[i].length == 3
- 1 ≤ trips[i][0] ≤ 5
- 0 ≤ trips[i][1], trips[i][2] ≤ 109
- 1 ≤ capacity ≤ 2 * 109 (fits in a 32-bit signed integer)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)