☕ DSA Java Articles

Topics › Greedy Algorithms › Medium/Hard

Minimum number of platforms required for a railway

Medium TUF ID 548 A2ZSDE

Java source ↗ Edit this article ↗

Problem

A station serves n trains in one day. Train i arrives at time arr[i] and departs at time dep[i], with times written as HHMM integers (900 means 09:00, 1130 means 11:30). A train occupies a platform from its arrival to its departure, both moments included: if one train leaves at 1030 and another arrives at 1030, they need different platforms. Find the minimum number of platforms so that no train ever has to wait.

Constraints: 1 ≤ n ≤ 5 × 10^4, 0 ≤ arr[i] ≤ dep[i] ≤ 2359. No train stays past midnight.

Example 1

arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1200, 1120, 1130, 1900, 2000]
answer = 3          // at 11:00 the trains arriving at 9:40, 9:50 and 11:00 are all in the station

Example 2

arr = [900, 1100, 1235], dep = [1000, 1200, 1240]
answer = 1          // no two trains are ever in the station together

Reframing the question

The number of platforms needed is exactly the largest number of trains present at the same moment. It cannot be less, because those trains each need their own platform at that moment. It is also enough: assign platforms as trains arrive, giving each arriving train any free platform. If at most k trains are ever present, then whenever a train arrives at most k - 1 others are there, so one of k platforms is free.

So the task is: find the maximum overlap of n closed intervals [arr[i], dep[i]].

Approach 1: Brute force, count trains at every arrival

Intuition. The number of trains in the station only goes up when a train arrives. So the maximum must be reached at some arrival moment: take the moment with the most trains, then move back in time to the latest arrival among those trains; all of them have already arrived and none has left yet. Hence it is enough to check each arrival time arr[i] and count the trains j with arr[j] ≤ arr[i] ≤ dep[j].

A tempting but wrong shortcut is “for each train, count the trains whose interval overlaps it”. That overcounts: with trains [100, 1000], [100, 200] and [500, 600], the long train overlaps both others, yet the two short ones are never there together, so 2 platforms suffice, not 3. Counting at a single moment avoids this.

Algorithm.

  1. For each train i, set present = 0 and count every train j with arr[j] ≤ arr[i] ≤ dep[j].
  2. Keep the largest count.
static int bruteForce(int[] arr, int[] dep) {
    int n = arr.length, best = 0;
    for (int i = 0; i < n; i++) {
        int present = 0;
        for (int j = 0; j < n; j++) {
            if (arr[j] <= arr[i] && arr[i] <= dep[j]) present++;   // train j is in the station at time arr[i]
        }
        best = Math.max(best, present);
    }
    return best;
}

Complexity. Time O(n^2): every arrival is checked against every train. Space O(1).

Approach 2: Optimal, sort arrivals and departures separately

Intuition. Imagine walking along the timeline and keeping a counter of trains in the station: +1 at each arrival, -1 at each departure. The answer is the highest value the counter reaches. To walk the timeline we need all events in time order.

Here is the surprising part: we can sort arr and dep independently, breaking the pairing between a train’s arrival and its departure. That is fine because the counter at time t only depends on how many arrivals have happened and how many departures have happened, not on which train each event belongs to. Then we merge the two sorted lists like the merge step of merge sort, always processing the earlier event next.

When an arrival and a departure share the same time, process the arrival first. The departing train still occupies its platform at that minute, so for that instant both trains are present, matching the rule in the statement.

Algorithm.

  1. Copy and sort arr into a and dep into d.
  2. i = j = 0, onPlatform = best = 0.
  3. While i < n:
    • If a[i] ≤ d[j], a train arrives: onPlatform++, i++, update best.
    • Otherwise a train leaves: onPlatform--, j++.
  4. Return best.

Once all arrivals are processed the counter can only fall, so we can stop without draining the departures. And j never runs past the end: the k-th smallest departure is never earlier than the k-th smallest arrival, so whenever j catches up with i, the comparison a[i] ≤ d[j] picks the arrival.

static int optimal(int[] arr, int[] dep) {
    int[] a = arr.clone(), d = dep.clone();
    Arrays.sort(a);
    Arrays.sort(d);
    int n = a.length, i = 0, j = 0, onPlatform = 0, best = 0;
    while (i < n) {
        if (a[i] <= d[j]) {          // next event is an arrival; on a tie it goes first (both trains need a platform)
            onPlatform++;
            i++;
            best = Math.max(best, onPlatform);
        } else {                     // next event is a departure, which frees a platform
            onPlatform--;
            j++;
        }
    }
    return best;
}

Dry run on Example 1. Sorted, a = [900, 940, 950, 1100, 1500, 1800] and d = [910, 1120, 1130, 1200, 1900, 2000].

event time onPlatform best
arrive 900 1 1
depart 910 0 1
arrive 940 1 1
arrive 950 2 2
arrive 1100 3 3
depart 1120 2 3
depart 1130 1 3
depart 1200 0 3
arrive 1500 1 3
arrive 1800 2 3

All arrivals are processed, so the answer is 3.

Complexity. Time O(n log n) for the two sorts; the merge is O(n). Space O(n) for the copies, which keep the caller’s arrays untouched.

Because times are bounded by 2359, a counting alternative also exists: add +1 at arr[i] and -1 at dep[i] + 1 in an array of size 2361, then take the maximum prefix sum. That is O(n + T) for T possible times. It is a nice trick when the time range is small, but the sorting method works for any time values.

Edge cases and pitfalls