Task — Minimum platforms

You are given two arrays of arrival and departure times of trains at a railway station. Write a script to find out the minimum number of platforms needed so that no train needs to wait.

Examples

Example 1:
Input: @arrivals   = (11:20, 14:30)
       @departures = (11:50, 15:00)
Output: 1
    The 1st arrival of train is at 11:20 and this is the 
    only train at the station, so you need 1 platform.
    Before the second arrival at 14:30, the first train 
    left the station at 11:50, so you still need only 1 
    platform.

Example 2:
Input: @arrivals   = (10:20, 11:00, 11:10, 12:20, 16:20, 
                      19:00)
       @departures = (10:30, 13:20, 12:40, 12:50, 20:20, 
                      21:20)
Output: 3
    Between 12:20 and 12:40, there would be at least 3 
    trains at the station, so we need minimum 3 platforms.

Analysis

My solution is to make a hash %trains with all events - ie arrival and departure times - as the keys. The value of each hash element is the change in platforms needed, ie +1 for an arrival and -1 for a departure.

There could be two events happening at the same time, so the hash key needs to be suffixed with a unique number. Also, it would be dangerous for a train to arrive in a platform at the same time as an earlier train leaves, so we need consider arrivals at a given time before departures and the hash keys have to sort arrivals at a given time before departures. So a typical hash key is 12:20-a3 (the 4th train arrives at 12:20) or 12:30-d6 (the 5th train departs at 12:30).

It's then just a case of pacing through the sorted hash, adding a platform for an arrival and subtracting one for a departure, and keeping track of the largest number of platforms needed.

Try it 

#!/usr/bin/perl

# Peter Campbell Smith - 2021-08-30
# PWC 128 task 2

use utf8;
use v5.26;
use strict;
use warnings;

minimum_platforms (['10:20', '11:00', '11:10', '12:20', '16:20', '19:00'],
    ['10:30', '13:20', '12:40', '12:50', '20:20', '21:20']);

sub minimum_platforms {
    
    my (@arrivals, @departures, $train, %trains, $max_platforms, $now_platforms, $event);
    
    @arrivals   = @{$_[0]};
    @departures = @{$_[1]};

    # create the hash
    for $train (0 .. $#arrivals) {
        $trains{"$arrivals[$train]-a$train"} = 1;
    }
    for $train (0 .. $#departures) {
        $trains{"$departures[$train]-d$train"} = -1;
    }

    # loop over the events in time order
    $max_platforms = 0;
    $now_platforms = 0;   # number of platforms needed after each event

    for $event (sort keys %trains) {
        $now_platforms += $trains{$event};
        $max_platforms = $now_platforms if $now_platforms > $max_platforms;
    }

    # show input and output
    print 'Arrivals:   ' . join(' ', @arrivals) . "\nDepartures: " . join(' ', @departures)  . 
        "\n\nWe need $max_platforms platforms\n";
}

last updated 2026-03-08 — 15 lines of code

Output

Arrivals:   10:20 11:00 11:10 12:20 16:20 19:00
Departures: 10:30 13:20 12:40 12:50 20:20 21:20

We need 3 platforms