Quick Overview

Minimize a bus fleet when trips have origin and destination stations, tracking when buses become available at the correct departure station.

Find the Minimum Bus Fleet with Station Constraints

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

A bus schedule specifies the departure time, arrival time, departure station, and arrival station of every trip. Find the minimum number of buses that can serve all trips while respecting both time and location. ### Function Contract Implement `minimum_station_buses(trips) -> int`. Each trip is an integer array `[departure, arrival, origin, destination]`. A bus ending a trip at station `s` at time `t` may next serve a trip only if that trip departs from station `s` at or after `t`. Return the minimum total number of buses in the fleet. ### Constraints and Clarifications Use these explicit practice assumptions: buses may be placed at any stations before service begins, there is no turnaround time, and buses cannot move between stations except by serving a listed trip. Every listed trip must be served exactly once. Station identifiers have no distance or travel-time meaning. - `0 <= len(trips) <= 200000`. - `0 <= departure < arrival <= 1000000000`. - Station identifiers are integers from `0` through `1000000000`, inclusive. - A trip may start and end at the same station. - Trips may be unsorted, and identical records still represent distinct trips. - A bus arriving at the exact departure time is available for that departure at the same station. - 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, 4, 1, 2], [4, 7, 2, 1], [4, 6, 1, 2]] Output: 2 ``` The bus from the first trip is at station `2` at time `4`, so it can serve the second trip. Another bus must be available at station `1` for the third trip. ```text trips = [[0, 2, 1, 2], [3, 5, 1, 2]] Output: 2 ``` The trips do not overlap, but the first bus finishes at station `2`. It cannot serve the later trip from station `1` because empty repositioning is not allowed. ```hint Availability includes a station The globally earliest finishing bus may be in the wrong place. Consider which availability information a departure from one particular station actually needs. ```

Overview: Minimize a bus fleet when trips have origin and destination stations, tracking when buses become available at the correct departure station.

A bus schedule lists, for every trip, its departure time, arrival time, departure station and arrival station. Find the minimum number of buses that can serve all trips while respecting both time and location. Implement `minimum_station_buses(trips) -> int`. Each trip is an integer array `[departure, arrival, origin, destination]`, meaning a bus leaves station `origin` at time `departure` and reaches station `destination` at time `arrival`. A bus ending a trip at station `s` at time `t` may next serve a trip only if that trip departs from station `s` at or after `t`. Return the minimum total number of buses in the fleet. ### Practice assumptions These are explicit and part of the contract: buses may be placed at any stations before service begins, there is no turnaround time, and buses cannot move between stations except by serving a listed trip. Every listed trip must be served exactly once. Station identifiers have no distance or travel-time meaning. ### Constraints - `0 <= len(trips) <= 200000`. - `0 <= departure < arrival <= 1000000000`. - Station identifiers are integers from `0` through `1000000000`, inclusive. - A trip may start and end at the same station. - Trips may be unsorted, and identical records still represent distinct trips. - A bus arriving at the exact departure time is available for that departure at the same station. - Return `0` for an empty schedule. - Aim for `O(n log n)` time or better, where `n` is the number of trips. ### Output Return a single integer: the minimum fleet size. It is at least `0` and at most `len(trips)`, so the answer and every input value fit comfortably in a signed 32-bit integer; no value in this problem can exceed 2^31 - 1. ### Examples Example 1: ```text trips = [[0, 4, 1, 2], [4, 7, 2, 1], [4, 6, 1, 2]] Output: 2 ``` The bus from the first trip is at station `2` at time `4`, so it can serve the second trip. Another bus must be available at station `1` for the third trip. Example 2: ```text trips = [[0, 2, 1, 2], [3, 5, 1, 2]] Output: 2 ``` The trips do not overlap, but the first bus finishes at station `2`. It cannot serve the later trip from station `1` because empty repositioning is not allowed.

Constraints

  • 0 <= len(trips) <= 200000.
  • Each trip is an integer array [departure, arrival, origin, destination].
  • 0 <= departure < arrival <= 1000000000.
  • Station identifiers are integers from 0 through 1000000000, inclusive.
  • A trip may start and end at the same station.
  • Trips may be unsorted, and identical records still represent distinct trips.
  • A bus arriving at the exact departure time is available for that departure at the same station.
  • Buses may be placed at any stations before service begins, there is no turnaround time, and buses cannot move between stations except by serving a listed trip.
  • Every listed trip must be served exactly once, and station identifiers have no distance or travel-time meaning.
  • Return 0 for an empty schedule.
  • Aim for O(n log n) time or better, where n is the number of trips.

Examples

Input: ([],)

Expected Output: 0

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

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

Expected Output: 1

Explanation: A single trip that starts and ends at station 0 still needs exactly one bus.

Hints

  1. The globally earliest finishing bus may be in the wrong place. Consider which availability information a departure from one particular station actually needs.
  2. Each trip contributes two separate moments to the day: the instant a bus must leave one station, and the instant a bus becomes free at another. Handling those moments in time order is enough to decide every trip.
  3. When two moments share a timestamp, the statement already fixes which one wins: a bus arriving at the exact departure time is available for that departure.

Loading coding console...

Show the approach

Approach

Algorithm. Turn every trip into two timeline events: an arrival event (arrival, kind=0, destination) that makes one bus idle at the destination station, and a departure event (departure, kind=1, origin) that consumes one idle bus at the origin station. Sort all 2n events by time, breaking ties so that arrivals (kind 0) are processed before departures (kind 1) at the same timestamp -- the statement fixes this tie-break by saying a bus arriving at the exact departure time is available for that departure. Sweep the sorted events keeping a hash map idle[station] = number of buses currently standing at that station. On an arrival, increment idle[destination]. On a departure, if idle[origin] > 0 decrement it (reuse a bus already standing there), otherwise pay for a brand-new bus and increment the answer. The answer is the number of departures that found no bus standing at their origin.

Invariant. Just before each event at time t is processed, idle[s] equals the number of buses that are parked at station s, idle, and available for any departure from s at a time >= t; the running counter buses equals the number of buses introduced so far, and every trip already departed has been assigned to exactly one bus.

Correctness. Reuse is never worse than introducing a bus. At a departure from station s at time d, an idle bus A standing at s and a brand-new bus B placed at s are interchangeable: both are at station s and free at time d, and B has no earlier obligations. So if an optimal schedule introduces B for this departure while A waits, swapping the futures of A and B yields a schedule with the same fleet size in which the waiting bus takes this trip. Applying the exchange left-to-right over the sorted events turns any optimal schedule into the greedy one without increasing the count, so greedy is optimal. It is also feasible: a bus is only reused at the exact station where it was last left and only at a time >= its arrival there. Lower bound intuition: each counted departure had zero buses free at its origin at that instant, so it genuinely forced a new vehicle. Note that buses at other stations are irrelevant to a departure -- the globally earliest-finishing bus may be in the wrong place -- which is why availability is tracked per station rather than in a single global heap.

Edge cases. An empty schedule returns 0 (handled by the early return, and also naturally by the empty sweep). A trip whose origin equals its destination leaves the bus where it started, and a set of such trips degenerates to counting maximum simultaneous intervals at that station. Identical trip records are distinct trips and each consumes its own bus-slot. Input order is irrelevant because the sweep sorts. Because departure < arrival strictly, a trip's own arrival event can never precede its departure event, so a trip can never be reused by itself. Station identifiers up to 1000000000 are used only as hash keys and carry no geometry. All quantities fit in signed 32-bit integers (times and ids <= 1000000000, answer <= n <= 200000).

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