Find the Minimum Bus Fleet with Station Constraints

A bus schedule specifies the departure time, arrival time, departure station, and arrival station of every trip. Find the minimum number of buses that can serve all trips while respecting both time and location.

Function Contract

Implement minimum_station_buses(trips) -> int. Each trip is an integer array [departure, arrival, origin, destination].

A bus ending a trip at station s at time t may next serve a trip only if that trip departs from station s at or after t. Return the minimum total number of buses in the fleet.

Constraints and Clarifications

Use these explicit practice assumptions: buses may be placed at any stations before service begins, there is no turnaround time, and buses cannot move between stations except by serving a listed trip. Every listed trip must be served exactly once. Station identifiers have no distance or travel-time meaning.

• 0 <= len(trips) <= 200000.
• 0 <= departure < arrival <= 1000000000.
• Station identifiers are integers from 0 through 1000000000, inclusive.
• A trip may start and end at the same station.
• Trips may be unsorted, and identical records still represent distinct trips.
• A bus arriving at the exact departure time is available for that departure at the same station.
• Return 0 for an empty schedule.
• Aim for O(n log n) time or better, where n is the number of trips.

Examples

trips = [[0, 4, 1, 2], [4, 7, 2, 1], [4, 6, 1, 2]]
Output: 2

The bus from the first trip is at station 2 at time 4, so it can serve the second trip. Another bus must be available at station 1 for the third trip.

trips = [[0, 2, 1, 2], [3, 5, 1, 2]]
Output: 2

The trips do not overlap, but the first bus finishes at station 2. It cannot serve the later trip from station 1 because empty repositioning is not allowed.