Minimum Platforms Problem

The problem, simply

You get the arrival time and the departure time of n trains for one day. A train needs a platform from the minute it arrives up to and including the minute it leaves. So if one train leaves at 10:00 and another arrives at 10:00, they need two different platforms.

Give back the smallest number of platforms so that no train ever has to wait.

A story to remember it

Picture it

Examples

Way 1: the simple way

The busiest moment always starts when some train arrives. So for each train, stand at its arrival time and count how many trains are in the station right then.

1. For each train i, count the trains j with arr[j] <= arr[i] <= dep[j]. That count includes train i itself.
2. The answer is the biggest count.

class Solution {
    public int findPlatforms(int[] arr, int[] dep) {
        int n = arr.length, best = 0;
        for (int i = 0; i < n; i++) {
            int here = 0;                                  // trains in the station when train i arrives
            for (int j = 0; j < n; j++) {
                if (arr[j] <= arr[i] && arr[i] <= dep[j]) here++;
            }
            best = Math.max(best, here);
        }
        return best;
    }
}

How long it takes: every train is checked against every train, O(n^2). Extra room: two counters, O(1).

Way 2: the clever way

Do what the teacher at the door does. You only need the events of the day in time order: an arrival adds one train, a departure removes one. Which train is which does not matter, so you can sort the arrival times and the departure times separately.

1. Sort arr and sort dep.
2. Put i at the first arrival and j at the first departure. platforms = 0.
3. If arr[i] <= dep[j], the next event is an arrival: platforms++, update the best, i++. The <= makes an arrival count before a departure at the same minute.
4. Otherwise the next event is a departure: platforms--, j++.
5. Stop when every train has arrived. The best count is the answer.

The line on the ruler is the time of the event we just handled.

import java.util.Arrays;

class Solution {
    public int findPlatforms(int[] arr, int[] dep) {
        int n = arr.length;
        Arrays.sort(arr);
        Arrays.sort(dep);
        int i = 0, j = 0, platforms = 0, best = 0;
        while (i < n) {
            if (arr[i] <= dep[j]) {          // a train comes in (first on a tie)
                platforms++;
                best = Math.max(best, platforms);
                i++;
            } else {                          // a train leaves
                platforms--;
                j++;
            }
        }
        return best;
    }
}

How long it takes: the two sorts are O(n log n) and the walk is O(n). Extra room: O(1) beyond sorting in place. If you may not change the input, copy the arrays first for O(n).

Watch out for

• Sorting the two lists separately is fine. It breaks the link between a train's arrival and its departure, but the count of trains in the station at every moment stays the same.
• Some inputs have trains that leave after midnight, like arriving at 2350 and leaving at 0010. Add 2400 to such departures first.
• You can stop once i == n. After the last arrival, the count only goes down.
• With HHMM times, a train from 900 to 1000 lasts 60 minutes, not 100. That does not matter here because we only compare times.

What interviewers ask next

• Return which platform each train uses. Sort trains by arrival and keep a min-heap of the departure times of busy platforms. If the earliest one is free before the new train comes, reuse it; otherwise open a new platform.
• The same question for meetings and rooms is "Meeting Rooms II". The same code works.
• What if times are small whole numbers, like minutes in a day? Use a difference array: add 1 at each arrival and subtract 1 just after each departure, then take running sums. That is O(n + T) with no sort.
• Can you write it with one list of events? Make pairs (time, +1) for arrivals and (time, -1) for departures, sort by time with arrivals first on ties, and keep a running sum.

Remember this

Grown-up words: the counter at the door is a sweep line, the two sorted lists walked together are two pointers, the highest count is the maximum overlap of intervals, and the coat hooks are the platforms.