Maximum trains for which stoppage can be provided

The problem, simply

A station has m platforms. You get n trains. Each train has an arrival time, a leaving time and the one platform it must use. A platform can hold only one train at a time. A train may arrive at the same moment the previous train on its platform leaves.

Some trains may have to skip the station. Give back the largest number of trains that can stop.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every group of trains. A group is fine if no two trains in it want the same platform at overlapping times. Keep the biggest fine group.

1. For each mask from 0 to 2^n - 1, look at the trains whose bit is on.
2. Check every pair in the group. Same platform and overlapping times means the group is broken.
3. Remember the size of the biggest unbroken group.

class Solution {
    // each train is {arrive, leave, platform}
    public int maxStoppedTrains(int m, int[][] trains) {
        int n = trains.length, best = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            boolean fine = true;
            for (int i = 0; i < n && fine; i++) {
                if ((mask & (1 << i)) == 0) continue;
                for (int j = i + 1; j < n && fine; j++) {
                    if ((mask & (1 << j)) == 0) continue;
                    int[] a = trains[i], b = trains[j];
                    boolean samePlatform = a[2] == b[2];
                    boolean overlap = a[0] < b[1] && b[0] < a[1];
                    if (samePlatform && overlap) fine = false;
                }
            }
            if (fine) best = Math.max(best, Integer.bitCount(mask));
        }
        return best;
    }
}

How long it takes: 2^n groups and up to n^2 pairs each, so O(2^n * n^2). Twenty five trains is already too many. Extra room: a few counters, O(1).

Way 2: the clever way

Platforms do not affect each other, so each platform is its own little puzzle: fit as many non-overlapping trains as possible. For that puzzle, the best first pick is the train that leaves earliest. It frees the platform soonest, so it can never block more trains than any other choice would.

You do not even need to split the trains by platform. Sort all trains by leaving time, and keep a small table that says when each platform is free again.

1. Sort the trains by leaving time.
2. Start with every platform free at any time.
3. For each train in order: if it arrives no earlier than its platform's free time, stop it, count it, and set the platform's free time to this train's leaving time. Otherwise it skips the station.

The line on the ruler shows when the platform of the current train is free again.

import java.util.Arrays;

class Solution {
    // each train is {arrive, leave, platform}, platforms are numbered 1 to m
    public int maxStoppedTrains(int m, int[][] trains) {
        int[][] t = trains.clone();
        Arrays.sort(t, (x, y) -> Integer.compare(x[1], y[1]));  // earliest leaver first
        int[] freeAt = new int[m + 1];
        Arrays.fill(freeAt, Integer.MIN_VALUE);                  // every platform starts free
        int count = 0;
        for (int[] tr : t) {
            int p = tr[2];
            if (tr[0] >= freeAt[p]) {                             // fits after the last train here
                count++;
                freeAt[p] = tr[1];
            }
        }
        return count;
    }
}

How long it takes: sorting is O(n log n), the walk is O(n), and filling the table is O(m), so O(n log n + m). Extra room: one free time per platform, O(m), plus the sorted copy of the trains.

Watch out for

• Read the touching rule. Here a train may arrive exactly when the last one leaves, so the check is >=. If the problem says they clash, use >.
• HHMM times like 1030 compare correctly as numbers, but you cannot subtract them to get minutes.
• Ignore trains whose platform number is bigger than m, or check the range before indexing the table.
• The answer counts trains, not platforms in use.

What interviewers ask next

• Why is earliest leaving time safe? Take any best plan for one platform. Swap its first train for the earliest leaver. The swap frees the platform no later, so every other train in the plan still fits, and the count is the same.
• What if a train can use any free platform? Sort by leaving time and give each train the platform that became free most recently but still before it arrives. A sorted set of free times does this in O(n log m).
• What if every train pays a different fee and you want the most money? Greedy breaks. Sort by leaving time and use dynamic programming with binary search for the last train that fits, per platform.
• How many platforms would you need so that no train skips? That is the Minimum Platforms problem: sort arrivals and departures and count the busiest moment.

Remember this

Grown-up words: the swings are platforms, a child's turn is an interval, saying yes to the one who finishes first is the earliest finish time greedy, and the whole puzzle on one platform is the activity selection problem.