Find Minimum Platforms Needed to Avoid Delay in the Train Arrival

Problem

The objective is to identify the minimal number of train platforms necessary for the railway station, as all trains arriving and departing reach the railway station. We have two arrays that show trains that cease arriving and departing time.

Sample Input

Trains arrival   = { 200, 210, 300, 320, 350, 500 }
Trains departure = { 230, 340, 320, 430, 400, 520 }

Sample Output

2

Approach

The goal is to take all occurrences into account in sequence. Once the event is sorted, track the number of trains that have arrived but have not gone at any moment. Sort train timings of arrival and departure.

Create two variables i =0 and j =0 and a plat variable with the current count platform. Run a loop while i < n and j < n and compare the array's ith element to the jth departure element. If the time of arrival is less than or equal to the start, then another platform is needed, such that the number of platforms increases, i.e. plat+ + and i increases.

If the time of arrival exceeds the departure, fewer platforms are necessary so that the number of platforms decreases and increase j. Update answer, i.e., = max (ans, plat) .

Python Programming

def findPlatform(arrival, departure, n):

   # Sort arrival and
   # departure arrays
   arrival.sort()
   departure.sort()
   plat = 1
   ans = 1
   i = 1
   j = 0

   while (i < n and j < n):

       # If next event in sorted
       # order is arrival,
       # increment count of
       # platforms
       if (arrival[i] <= departure[j]):

           plat += 1
           i += 1

       elif (arrival[i] > departure[j]):

           plat -= 1
           j += 1

       # update the answer
       if (plat > ans):
           ans = plat

   return ans


arrival = [900, 940, 950, 1100, 1500, 1800]
departure = [910, 1200, 1120, 1130, 1900, 2000]
n = len(arrival)

print("Minimum Number = ",
   findPlatform(arrival, departure, n))

Output

Minimum Number = 3

C++ Programming

#include <algorithm>
#include <iostream>
using namespace std;
int solve(int arrival[], int departure[], int n)
{

   // Sort arrival and departure arrays
   sort(arrival, arrival + n);
   sort(departure, departure + n);
   int plat = 1, ans = 1;
   int i = 1, j = 0;
   while (i < n && j < n) {

       // If next event in sorted order is arrival,
       // increment count of platforms needed

       if (arrival[i] <= departure[j]) {
           plat++;
           i++;
       }

       // Else decrement
       else if (arrival[i] > departure[j]) {
           plat--;
           j++;
       }

       // update ans
       if (plat > ans)
           ans = plat;
   }
   return ans;
}
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 << "Minimum number = "
       << solve(arrival, departure, n);
   return 0;
}

Output

Minimum number = 3

C# Programming

using System;

class Solution {
   static int solve(int[] arrival, int[] departure, int n)
   {
       Array.Sort(arrival);
       Array.Sort(departure);
       int plat = 1, ans = 1;
       int i = 1, j = 0;

       while (i < n && j < n) {
           // If next event in sorted order
           // is arrival, increment count
           // of platforms
           if (arrival[i] <= departure[j])
           {
               plat++;
               i++;
           }
           // Else decrement
           else if (arrival[i] > departure[j])
           {
               plat--;
               j++;
           }

           // Update ans if needed
           if (plat > ans)
               ans = plat;
       }
       return ans;
   }

   public static void Main()
   {
       int[] arrival = { 900, 940, 950, 1100, 1500, 1800 };
       int[] departure = { 910, 1200, 1120, 1130, 1900, 2000 };
       int n = arrival.Length;

       Console.Write("Minimum number = "
                   + solve(arrival, departure, n));
   }

}

Output

Minimum number = 3

People are also reading:

• WAP to print the truth table for XY+Z
• Print the Following Pattern
• Calculate sum and average of three numbers
• Python Program to Find LCM
• Program to Find the Sum of Natural Numbers
• Check whether the entered number is prime or not
• Display a message on screen
• WAP to Calculate Simple Interest
• Calculate the sum of two numbers
• WAP to print the 1 to 10 Multiples of a Number