Find the Minimum Fleet for a Bus Timetable

A bus operator must run every trip in a schedule. Each trip has a departure time and an arrival time. Find the minimum number of buses needed to cover all trips.

Function Contract

Implement minimum_buses(trips) -> int, where trips is an array of integer pairs [departure, arrival].

A bus can run at most one trip at a time. In this version, locations do not restrict reuse: after finishing a trip at time t, a bus can start any trip departing at or after t. Return only the minimum fleet size; do not return a bus assignment.

Constraints and Clarifications

For this exercise, times are comparable integer units on one timeline. No turnaround time is required. A trip occupies the half-open interval [departure, arrival), so an arrival at the same time as another departure permits reuse.

• 0 <= len(trips) <= 200000.
• 0 <= departure < arrival <= 1000000000 for every trip.
• The input may be unsorted.
• Identical pairs represent distinct trips that must each be served.
• 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, 10], [5, 8], [8, 12], [10, 15]]
Output: 2

One bus can run [0, 10] and then [10, 15]. A second can run [5, 8] and then [8, 12].

trips = [[4, 7], [1, 4], [7, 9]]
Output: 1

A single bus serves the trips in chronological order, reusing it at both equal-time boundaries.