Fewest Buses Needed to Cover Every Scheduled Trip

A transit operator has a list of scheduled trips, each with a start time and an end time, and a bus can run only one trip at a time. Return the smallest number of buses that can cover every trip.

Function Signature

def min_buses(trips: list[list[int]]) -> int:

Rules

• trips[i] = [start, end] with start < end. The bus running trip i is busy from start up to, but not including, end.
• A bus that finishes a trip at time t can start another trip at time t.
• Any free bus can take any trip; travel between the end of one trip and the start of the next is not modeled.

Constraints

• 1 <= len(trips) <= 10^5
• 0 <= start < end <= 10^9 for every trip

Examples

Example 1

Input: trips = [[1, 4], [2, 5], [7, 9], [3, 6]]
Output: 3

At time 3, the trips [1, 4], [2, 5] and [3, 6] are all running, so three buses are needed.

Example 2

Input: trips = [[1, 3], [3, 5], [5, 8]]
Output: 1

Each trip starts exactly when the previous one ends, so one bus runs all three.

Example 3

Input: trips = [[2, 10], [3, 4], [4, 6], [7, 8]]
Output: 2

The long trip needs its own bus, and the other three never overlap one another.