Maximum Trains for Given Stations and Time

Maximum Trains for Given Stations and Time is a classic scheduling problem dressed up as a railway. Underneath, it is the same greedy move that solves "meeting rooms" and "minimum platforms": process events in the right order and assign each one to a resource that is already free.

The slow way first

The brute-force instinct is to try every assignment of trains to platforms — for each train, branch over which platform it could go on. That explodes to roughly O(platforms^n) combinations, which is hopeless for anything but a handful of trains.

The question to ask: is there an order in which a simple, never-reconsider choice is always safe? For interval scheduling, the answer is yes — and the right order is by departure time.

The idea: sort by departure, fit greedily

Sort the trains so the one that leaves earliest comes first. Walk through them in that order. For each train, look for a platform whose last train has already departed by the time this train arrives. If you find one, put the train there and update when that platform next becomes free. If no platform is free, that train cannot be served.

Why departure order? Freeing up a platform as soon as possible leaves the most room for later trains. Picking the earliest-departing train first is the choice that never blocks a future train it did not have to.

Walk through it

Step through the animation. The pointer scans the departure-sorted trains left to right. Two platforms track when they next become free. Each train slots onto the first platform whose free time has passed (arrive >= free_at[p]), and the placed count ticks up. Notice [5, 8] reusing P2 at exactly time 5 — equal times are allowed because one train has fully departed.

Pseudocode

sort trains by departure time (earliest first)
free_at = [-infinity for each platform]   # when each platform is next free
placed = 0
for each train (arrive, depart):
    for each platform p:
        if arrive >= free_at[p]:           # this platform is free in time
            free_at[p] = depart            # it is now busy until depart
            placed += 1
            stop scanning platforms
return placed

The Python solution

def max_trains(trains, platforms):
    trains.sort(key=lambda t: t[1])
    free_at = [float("-inf")] * platforms
    placed = 0
    for arrive, depart in trains:
        for p in range(platforms):
            if arrive >= free_at[p]:
                free_at[p] = depart
                placed += 1
                break
    return placed

• Line 2 sorts by t[1], the departure time — the heart of the greedy choice.
• free_at[p] holds the time platform p next becomes available; it starts at -infinity so every platform is free at the start.
• For each train we scan platforms and take the first one where arrive >= free_at[p].
• When we place a train, the platform is busy until depart, so we set free_at[p] = depart and break so the train lands on exactly one platform.
• placed is the running answer; a train that finds no free platform simply is not counted.

Complexity

The sort is the costly part at O(n log n); the assignment loop is linear in trains times platforms. Extra space is just the free_at array, one slot per platform.

When this pattern shows up

Practice