Greedy: Get the minimum platforms needed to avoid delay in the train arrival.

Problem Statement:

You are given an array of arrival and departure timings for train at a station.

You need to find the minimum umber of platforms required such that no train waits.

Example

arrival[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
departure[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output: 3

This is because, in the time interval from 11 to 12 there are 3 trains present at the station.

Solution

We can solve this problem in 2 different ways.

Method 1: Brute Force approach O(n^2)

We can get the arrival and departure for each train and compare it with the schedule.

The maximum of all these numbers will be the total platform needed.

Example:

           Arrival Time        Departure Time
Train-1         9:00                9:10
Train-2         9:40                12:00 <-
Train-3         9:50                11:20 <-
Train-4        11:00                11:30 <-
Train-5        15:30                19:15
Train-6        18:00                20:00

Method 2: Greedy Approach O(log(n)) time

If we observe the question, we need to find out how many trains will have an overlapping schedule.

It means, if there is a train, Train A, and we need to find if there are any trains arriving before the arrival of a train.

So we need to sort both of the arrays combined. Then we need to check if there are any trains whose departures are after the arrival of a train.

After sorting, we will keep track of the platforms needed.

 Time      Event     Total Platforms Needed                
 9:00      Arrival              1            
 9:10      Departure            0            
 9:40      Arrival              1            
 9:50      Arrival              2            
 11:00     Arrival              3            
 11:20     Departure            2            
 11:30     Departure            1            
 12:00     Departure            0            
 15:00     Arrival              1            
 18:00     Arrival              2            
 19:00     Departure            1            
 20:00     Departure            0   

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>

using namespace std;

int get_min_num_platform_brute_force(int arrival[], int departure[], int n)
{
  int platforms = 1;
  int result = 1;
  for(int i = 0; i<n; i++)
  {
    platforms = 1;
    for(int j = i+1; j<n; j++)
    {
      if ((arrival[i] >= arrival[j] && arrival[i] <= departure[j]) || (arrival[j] >= arrival[i] && arrival[j] <= departure[i])) {
        platforms++;
      }
    }
    result = max(result, platforms);
  }
  return result;
}

int get_min_num_platform_greedy(int arrival[], int departure[], int n)
{

  int platforms = 1;
  int result = 1;

  sort(arrival, arrival + n);
  sort(departure, departure + n);

  int i=1;
  int j=0;

  while(i<n && j<n)
  {
    if(arrival[i]<=departure[j])
    {
      platforms++;
      i++;
    }else if(departure[j]<arrival[i]){  // else decrease the number of platforms required
      platforms--;
      j++;
    }
    result = max(platforms,result);
  }

  return result;
}

int main()
{
    int arrival[] = { 900, 940, 950, 1100, 1500, 1800 };
    int departure[] = { 910, 1200, 1120, 1130, 1900, 2000 };
    int n = sizeof(arrival) / sizeof(arrival[0]);
    cout << "The min num of platform required using brute force approach are "
         << get_min_num_platform_brute_force(arrival, departure, n)<<endl;


    cout << "The min num of platform required using greedy approach are "
         << get_min_num_platform_greedy(arrival, departure, n)<<endl;
    return 0;
}

Output:

The min num of platform required using brute force approach are 3
The min num of platform required using greedy approach are 3