Solving a medium algorithm challenge step by step — Minimum Number of Platforms Required for a Railway Station

Hello 👋🏽, I came across the “Minimum Number of Platforms Required for a Railway” coding challenge and decided to share my solution.

I provide code implementations in JavaScript and C++ with clear explanations and time complexity analysis in the end. To fully understand this article, it is required that you have a working knowledge of basic programming concepts(variables, control structures, etc.).

The Question

Given the arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits.

The provided input is two arrays representing the arrival and departure times of trains that stop.
Note: The time values are in 24hr format.

Arrival = [ 900, 940, 950, 1100, 1500, 1800 ]
Departure = [ 910, 1200, 1120, 1130, 1900, 2000]

Output: 3 (A minimum of 3 platforms are needed so that no train waits)

Explanation

The question provides arrival and departure times of all trains that pass through a station with separate arrays.

The data in these arrays are linked by their indexes in these arrays. For example, say train A, owning index “0” of both arrays, arrives at 9:00 and departs at 9:10. There is a waiting period between each arrival and departure. We can assume this allows passengers to disembark and board the train, and by default, there is one platform that all the trains use.

The problem arises when multiple trains have overlapping wait times, which can cause a block in the single platform, causing the trains to queue. This means that trains ready to depart may be delayed by a waiting train in front of them; therefore, they must wait extra time as they can not jump the queue.

For example, if train B is ready to depart, and there is a waiting train A in front of it, train B must wait until train A leaves. The goal is to find the minimum number of platforms that won’t result in any delay from overlapping times.

The illustration below shows how three trains with overlapping times queue using one, two or three platforms.

Assuming the maximum number of trains that wait at a particular time is three, then three platforms are required to ensure that no train waits for another to leave before it can — the needed answer.

The Approach

Since we know that the maximum number of trains present together at the station at a particular time is also the minimum number of platforms required so that no train waits. We can chronologically simulate each train's arrival and departure and record the maximum number of trains present together throughout the simulation.

During this simulation, we use a virtual queue to represent trains at the station at each moment. The answer will be the maximum length(or size) of the queue encountered during the simulation.

This solution employs a virtual clock to keep track of the present time during the simulation. To know which trains have supposedly departed the station, we compare the departure times of the waiting trains with the present time.

If you are familiar with the conventional “queue” data structure, please note that the virtual queue being referred to here is different. It is only a means to store and delete items.

The list below is a high-level summary of the approach:

1. Sort the input data in ascending order, according to their arrival times. I.e. the earliest train comes first.
2. Create variables to store
   1. The virtual clock,
   2. The virtual queue and
   3. The maximum number of waiting trains seen at a particular time.
3. Loop through the sorted input (see step 1) from the beginning. Each current iteration of the loop represents the arrival of a train.
4. When a train arrives, the virtual clock is updated using the arrival time of the newly arrived train, signifying the present moment.
5. After updating the virtual clock, we check for supposedly departed trains and remove them from the virtual queue. This is achieved by comparing their departure times with the present time of the clock.
6. The newly arrived train is added to the queue, as it is presently at the station.
7. Suppose the virtual queue's current length (or size) is greater than any previously seen length, the “max” variable (created in step 2) is updated to this current length.
8. The “max” variable is returned as the answer at the end of the simulation (or loop).

JavaScript Solution

We begin by converting the input arrays into a single array of objects representing a train's data we will use in our solution to simplify the process. Below is an example of the format.

i.e {
arrivedAt: 900,
departsAt: 910
}

The helper function below, “makeTrainsArray”, creates an array of such objects. This helper function also sorts the array according to arrival time because the provided problem input is not guaranteed to be sorted.

Inputs:

Arrivals = [ 900, 940, 950, 1100, 1500, 1800 ]
Departures = [ 910, 1200, 1120, 1130, 1900, 2000]

// Makes a single trains array, sorted chronologically with their arrival times
function makeTrainsArray(arrivals, departures, n) {
    const trainsArr = new Array(n)
    for (let i = 0; i < n; i++) {
        trainsArr[i] = {
            arrivedAt: arrivals[i],
            departsAt: departures[i]
        }
    }

    // Sort data according to arrival time
    trainsArr.sort((a, b) => a.arrivedAt - b.arrivedAt)
    return trainsArr;
}

Next, we write function to find the minimum number of platforms required

function findMinimumPlatforms(arrivals, departures, n) {
    const trains = makeTrainsArray(arrivals, departures, n)


    let virtualClockTime = 0;
    let maxTrainsWaiting = 0;
    // Using a JavaScript set because deleting an item is straightforward, compared to arrays
    let virtualQueue = new Set();


    // Taking each train sequentially to simulate arrivals
    for (let newlyArrivedTrain of trains) {
        // Update present moment to the time of newly arrived train
        virtualClockTime = newlyArrivedTrain.arrivedAt;


        // Remove supposedly departed trains from the virtual queue…
        // … using the present time.
        for (let train of virtualQueue) {


            if (train.departsAt < virtualClockTime) {
                virtualQueue.delete(train)
            }
        }


        // Add newly arrived train to virtual queue
        virtualQueue.add(newlyArrivedTrain)


        // Keep track of the maximum number of trains queueing at this particular time
        maxTrainsWaiting = Math.max(maxTrainsWaiting, virtualQueue.size)
    }


    return maxTrainsWaiting;


}

C++ Solution

There’s an issue with the JavaScript solution. In order to check and remove supposedly departed trains from the virtual queue, all items in the queue are visited, including non-departed trains. This process can be optimised using a “min-heap”.

A min-heap, also known as a “priority queue”, is a data structure that always keeps a reference to the smallest item in the “heap”.

The smallest item— the top, can be easily “popped” out of the queue.

The image below visualises the structure of a min-heap when all departure times from the example are inserted:

(Resources on min-heap data structure are at the end of this article).

This min-heap structure is not present in JavaScript by default. You’d have to implement a class or use an external library to use it. We will not be doing that in this article.

However, we can use the priority_queue data type present in C++’s STL— Standard Template Library. This way, we can quickly check for supposedly departed trains and remove them without visiting every item in the queue.

Below is a C++ implementation of the same solution, but checking for departed trains is done using a min-heap.

#include <iostream>

// The next two imports can be reduced to #include <bits/stdc++.h>, depending on your compiler.
#include <algorithm> // We'll need this for sorting
#include <queue> // We'll need this for the priority queue (or min heap)

using namespace std;

struct TrainData {
    int arrivedAt;
    int departsAt;
};

// Helper function for sorting with arrival times
static bool compareArrivalTimes(TrainData trainA, TrainData trainB)
{
    return (trainA.arrivedAt < trainB.arrivedAt);
}

// Helper function to make a trains array sorted chronologically with their arrival times
TrainData* makeTrainsArray(int arrivals[], int departures[], int n) {
    TrainData* trains = new TrainData[n];

    for(int i = 0; i < n; ++i){
        // Make a new train data using the defined struct
        TrainData train;
        train.arrivedAt = arrivals[i];
        train.departsAt = departures[i];

        trains[i] = train;
    }

    sort(trains, trains + n, compareArrivalTimes);
    return trains;
}

Next, a function to find the minimum function to platforms required

int findMinimumPlatforms(int arrivals[], int departures[], int n) {
  const TrainData * trains = makeTrainsArray(arrivals, departures, n);

  int virtualClockTime = 0;
  int maxTrainsWaiting = 0;

  // Using a priority queue data structure for the virtual queue.
  priority_queue < int > virtualQueue;

  for (int i = 0; i < n; ++i) {
    // Update present moment to the time of newly arrived train
    virtualClockTime = trains[i].arrivedAt;

    // Remove supposedly departed trains from the virtual queue by using the present time.
    while (!virtualQueue.empty()) {
      int departureTime = virtualQueue.top() * -1;
      if (departureTime < virtualClockTime) {
        virtualQueue.pop();
      } else {
        // We can break out of the loop here because all departed trains have been removed.
        break;
      }

    }

    // Add newly arrived train to queue (note we are storing only the time in the priority queue)
    virtualQueue.push(trains[i].departsAt * -1);

    // Keep track of the maximum number of trains queueing at this particular time
    maxTrainsWaiting = maxTrainsWaiting > virtualQueue.size() ? maxTrainsWaiting : virtualQueue.size();

  }

  // Free up allocated memory ;)
  delete trains;
  return maxTrainsWaiting;
}

Analysing The Time Complexity

In this section, we analyse this solution's time complexity using “big O” notation.

Here are some things to note:

• Sorting processes generally perform an O(n * log(n)), and we used a sort function.
• The simulation loop performs an O(n) operation since every item is visited once. Denoting the length of the input as n.
• There is a nested while loop within the simulation loop, denoting the maximum length of the queue as m; this nested loop performs an O(m) operation.
• Inserting and deleting items from a priority queue, in the worst case, will perform an O(log(m)) operation.

In time complexity analysis, the big O of the algorithm is that of the worst operation performed within the algorithm.

At first glance, it seems like the sorting step is the most costly operation, making this an O(n * log(n)) solution.

Suppose m > log(n), the attention of the time complexity shifts from the sorting process to the simulation loop.

The simulation loop nests another loop— denoted with O(m). Hence the time complexity of the JavaScript solution is O(n * m).

The C++ solution performs “delete” operations on the min-heap, which has a time complexity of O(log(m)). We can then say the algorithm's time complexity is O(n * m * log(m)).

The main difference between the JavaScript C++ solution is that the JavaScript solution is guaranteed to complete all iterations of “m”. The C++ solution can break out of the loop once it has removed all departed trains— using the min-heap, it doesn’t waste time checking non-departed trains. Thus, it is seemingly more efficient.

Conclusion

When coming up with a brute force solution, it is helpful to determine how you understand the problem, what a working solution is and what would make a working solution. Then you can attempt translating that thought process into code with the help of data structures.

It is common for algorithm challenges to have multiple solutions. There are other solutions to this problem, including more efficient ones. It is okay if you come up with a different approach to this problem.

This article was written to help people get comfortable with data structures and algorithms and translate their thought processes into code to arrive at a solution.

I hope you enjoyed it. Thanks for reading.

Resources

To learn more about priority queues:
https://www.programiz.com/cpp-programming/priority-queue

You can practice your solution against test cases here:
https://practice.geeksforgeeks.org/problems/minimum-platforms-1587115620/1#

Big O Notation:
https://www.doabledanny.com/big-o-notation-in-javascript

Solution files on GitHub:
GitHub Repo