Quick Overview

Find the minimum number of buses needed for a timetable by tracking overlapping trips and allowing reuse at equal arrival and departure times.

Find the Minimum Fleet for a Bus Timetable

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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 ```text 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]`. ```text 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. ```hint Track when buses become available When processing departures in time order, determine whether any bus has already finished its previous trip. The input order need not be the execution order. ```

Overview: Find the minimum number of buses needed for a timetable by tracking overlapping trips and allowing reuse at equal arrival and departure times.

A bus operator must run every trip in a schedule. Each trip is an integer pair `[departure, arrival]` measured in comparable integer units on one shared timeline, and a bus can run at most one trip at a time. Locations do not restrict reuse: after a bus finishes a trip at time `t`, it may start any trip departing at or after `t`, and 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. Implement `minimum_buses(trips)` returning the minimum fleet size: the smallest number of buses that can cover all trips. Return only that count as an integer; do not return a bus assignment. The input may be unsorted, and 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. Every time is at most `1000000000` and the answer is at most `200000`, so no value can exceed `2^31 - 1`: a 32-bit `int` is sufficient in Java and C++. ### Constraints - `0 <= len(trips) <= 200000`. - `0 <= departure < arrival <= 1000000000` for every trip. - A trip occupies the half-open interval `[departure, arrival)`. - 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 ```text 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]`. ```text 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.

Constraints

  • 0 <= len(trips) <= 200000.
  • 0 <= departure < arrival <= 1000000000 for every trip.
  • A trip occupies the half-open interval [departure, arrival), so an arrival at the same time as another departure permits reuse.
  • 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.
  • All values fit in a signed 32-bit integer; no value exceeds 2^31 - 1.

Examples

Input: ([],)

Expected Output: 0

Explanation: An empty schedule needs no buses, so the answer is 0.

Input: ([[0, 1]],)

Expected Output: 1

Explanation: A single trip always needs exactly one bus.

Hints

  1. The input order need not be the execution order. Consider what the schedule looks like when you examine departures and arrivals in time order instead.
  2. At each departure, ask whether any bus has already finished its previous trip. A bus that arrives at exactly time t is free for a trip departing at t, so equal timestamps need a deliberate tie rule.
  3. You are asked only for a count, not for an assignment, so you never have to record which bus serves which trip.

Loading coding console...

Show the approach

Approach

The minimum fleet size equals the maximum number of trips that are simultaneously underway.

Lower bound: if k trips all contain some instant t, then no bus can serve two of them (a bus runs at most one trip at a time), so at least k buses are required; hence the answer is at least the peak concurrency. Upper bound: process departures in increasing time and always reuse a bus that is already free. Whenever a departure needs a brand new bus, every previously started trip that has not yet arrived is still underway at that departure time, so the number of buses ever allocated never exceeds the peak concurrency. The two bounds coincide, so the answer is exactly the peak concurrency.

The implementation computes that peak without materializing an assignment. It extracts the departures and the arrivals into two separate sorted arrays and walks them with two pointers i and j. Invariant: before each step, active equals the number of trips that have departed (indices < i) but not yet arrived (indices < j have arrived), i.e. active == i - j, and best is the maximum value active has taken. When starts[i] < ends[j], the next event in time is a departure, so active increases and best is updated; otherwise starts[i] >= ends[j], the next event is an arrival that frees a bus, so active decreases. Ordering arrivals before departures at equal timestamps is exactly the half-open rule [departure, arrival): a bus arriving at time t is available for a trip departing at t. Using <= instead of < there would model closed intervals and over-count chains such as [[0, 1], [1, 2]].

The loop terminates because each iteration advances i or j, and j can never pass i (active == i - j >= 0 while i < n guarantees an unmatched arrival exists), so ends[j] is always in range.

Edge cases: an empty schedule returns 0 via the early exit (and the loop body is never entered). A single trip returns 1. Identical pairs are treated as distinct trips because each contributes its own departure and arrival, so k copies of one interval yield k. Nested intervals are handled naturally since only the sorted multisets of endpoints matter, which also makes unsorted input irrelevant. Departures and arrivals are at most 1000000000 and only counters are accumulated, so no arithmetic can exceed 32-bit range.

Time complexity:
O(n log n)
Space complexity:
O(n)