Fewest Buses for a Station Schedule
HardGreedy ยท Snowflake
trips[i] = [depart, arrive, origin, dest] is a bus trip that leaves station origin at time depart and reaches station dest at time arrive. A bus that finishes a trip at station s at time t can next run any trip that leaves s at time t or later. A bus never travels without running a trip, and it may start at any station.
Return the fewest buses needed to run every trip, or 0 if there are none.
Example 1
- Input:
- trips = [[1, 3, 0, 1], [4, 6, 2, 0], [7, 9, 1, 2], [10, 12, 0, 1]]
- Output:
- 2
- Explanation
- One bus runs trips 0 and 2, since it reaches station 1 at time 3. Trip 1 leaves station 2, so a second bus runs it and then trip 3.
Example 2
- Input:
- trips = [[1, 2, 0, 1], [2, 3, 1, 0], [3, 4, 0, 1]]
- Output:
- 1
Example 3
- Input:
- trips = [[2, 5, 0, 1], [1, 3, 0, 1], [6, 8, 1, 2], [7, 9, 1, 0], [4, 7, 2, 0]]
- Output:
- 3
Constraints
0 <= trips.length <= 10^50 <= depart < arrive <= 10^90 <= origin, dest <= 10^5andorigin != desttripsmay be in any order