Minimum Station Tracks for a Schedule of Train Arrivals and Departures
Company: Bnsf
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A railway station must handle a schedule of trains. Each train occupies one station track from the moment it arrives until the moment it departs, and a track can hold only one train at a time. Given every train's arrival and departure time, return the minimum number of tracks the station needs so that every train has a track for its whole stay.
The report gives only the railway setting of this scheduling question; this version fixes the exact rules below.
### Function Signature
```python
def min_tracks(trains: list[list[int]]) -> int:
```
### Rules
- `trains[i] = [arrival, departure]` describes one train, with both times in whole minutes from the start of the schedule. The list is in no particular order.
- A train occupies a track during the half-open interval `[arrival, departure)`: a track that one train leaves at minute `t` can take another train arriving at minute `t`.
- A train stays on the same track for its whole stay.
- Return the smallest number of tracks for which every train can be given a track with no two trains on the same track at the same time.
### Constraints
- `1 <= len(trains) <= 10^5`
- `0 <= arrival < departure <= 10^9`, integers; every value fits in a 32-bit signed integer.
- Several trains may share an arrival or a departure time, and identical intervals may repeat.
### Examples
**Example 1**
```text
Input: trains = [[60, 150], [90, 120], [100, 200], [160, 180]]
Output: 3
```
From minute 100 to minute 119 the trains `[60, 150]`, `[90, 120]` and `[100, 200]` are all at the station, so three tracks are needed. No moment has four trains present: when `[160, 180]` arrives, only `[100, 200]` is still there.
**Example 2**
```text
Input: trains = [[10, 20], [20, 30], [30, 40]]
Output: 1
```
Each train departs at the minute the next one arrives, so one track serves all three.
**Example 3**
```text
Input: trains = [[50, 70], [10, 60], [50, 55], [65, 80]]
Output: 3
```
From minute 50 to minute 54, `[10, 60]`, `[50, 70]` and `[50, 55]` are all present. Later, `[65, 80]` overlaps only `[50, 70]`.
Overview: Given each train's arrival and departure time, compute the minimum number of station tracks needed so that no two trains occupy the same track at once, where a track freed at a given minute can take a train arriving that minute. It tests interval overlap reasoning, efficiency for up to a hundred thousand trains, and exact boundary handling.
Read the full Bnsf Software Engineer interview experience this question came from
A railway station must handle a schedule of trains. Each train occupies one station track from the moment it arrives until the moment it departs, and a track can hold only one train at a time. Given every train's arrival and departure time, return the minimum number of tracks the station needs so that every train has a track for its whole stay.
Implement `min_tracks(trains)`:
- `trains[i] = [arrival, departure]` describes one train, with both times in whole minutes from the start of the schedule. The list is in no particular order.
- A train occupies a track during the half-open interval `[arrival, departure)`: a track that one train leaves at minute `t` can take another train arriving at minute `t`.
- A train stays on the same track for its whole stay.
- Return the smallest number of tracks for which every train can be given a track with no two trains on the same track at the same time, as a single integer.
### Constraints
- `1 <= len(trains) <= 10^5`
- `0 <= arrival < departure <= 10^9`, integers; every value fits in a 32-bit signed integer.
- Several trains may share an arrival or a departure time, and identical intervals may repeat.
- The answer is at most `len(trains)`, so no input value or result exceeds 2^31 - 1 and 32-bit integers suffice in every language.
### Example 1
```text
Input: trains = [[60, 150], [90, 120], [100, 200], [160, 180]]
Output: 3
```
From minute 100 to minute 119 the trains `[60, 150]`, `[90, 120]` and `[100, 200]` are all at the station, so three tracks are needed. No moment has four trains present: when `[160, 180]` arrives, only `[100, 200]` is still there.
### Example 2
```text
Input: trains = [[10, 20], [20, 30], [30, 40]]
Output: 1
```
Each train departs at the minute the next one arrives, so one track serves all three.
Constraints
- 1 <= len(trains) <= 10^5
- 0 <= arrival < departure <= 10^9, integers; every value fits in a 32-bit signed integer.
- Several trains may share an arrival or a departure time, and identical intervals may repeat.
- Each train occupies the half-open interval [arrival, departure): a track that one train leaves at minute t can take another train arriving at minute t.
- The answer is at most len(trains), so no value exceeds 2^31 - 1.
Examples
Input: ([[60, 150], [90, 120], [100, 200], [160, 180]],)
Expected Output: 3
Explanation: Source example 1: three trains overlap from minute 100 to 119.
Input: ([[10, 20], [20, 30], [30, 40]],)
Expected Output: 1
Explanation: Source example 2: back-to-back chain; each departure frees the track for the arrival at the same minute.
Hints
- Think about the busiest moment of the schedule: how many trains are at the station then, and could fewer tracks ever be enough?
- The number of trains at the station can only go up when some train arrives, so those minutes are the ones worth examining.
- Mind the boundary: a train departing at minute t and a train arriving at minute t never need the station at the same moment.