Fewest Buses Needed to Cover Every Scheduled Trip
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: Given scheduled trips with start and end times, return the fewest buses needed so that no bus runs two trips at once, where a bus may start a trip the moment its previous one ends. It tests reasoning about maximum interval overlap and boundary handling.
A transit operator has a list of scheduled trips. Each trip has 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.
Implement `min_buses(trips)`, where `trips[i] = [start, end]`.
### Rules
- Every trip satisfies `start < end`. The bus running trip `i` is busy from `start` up to, but not including, `end` (the half-open interval `[start, 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.
- The trips are not necessarily given in sorted order, and the same `[start, end]` pair may appear more than once; each occurrence is a separate trip that needs a bus.
### Output
Return one integer: the minimum number of buses needed to run every trip.
### Constraints
- `1 <= len(trips) <= 10^5`
- `0 <= start < end <= 10^9` for every trip
- All times and the answer fit in a signed 32-bit integer (no value exceeds 2^31 - 1).
### Examples
**Example 1**
```text
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. Trip `[7, 9]` can reuse any of them.
**Example 2**
```text
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.
Constraints
- 1 <= len(trips) <= 10^5
- 0 <= start < end <= 10^9 for every trip
- Each trips[i] is a pair [start, end] of integers
- All times and the answer fit in a signed 32-bit integer
Examples
Input: ([[1, 4], [2, 5], [7, 9], [3, 6]],)
Expected Output: 3
Explanation: Source Example 1: [1, 4], [2, 5] and [3, 6] all run at time 3; [7, 9] reuses a freed bus.
Input: ([[1, 3], [3, 5], [5, 8]],)
Expected Output: 1
Explanation: Source Example 2: back-to-back chain where each start equals the previous end, so one bus runs all three (half-open reuse).
Hints
- A bus is busy on [start, end), so a trip that ends at time t and a trip that starts at time t never conflict.
- Look at the single moment when the most trips are running at once: could fewer buses than that ever be enough?
- Processing events in time order makes it easier to know how many buses are busy when a new trip begins.