Find Minimum Platforms Needed to Avoid Delay in the Train Arrival

Posted in

Find Minimum Platforms Needed to Avoid Delay in the Train Arrival
vinaykhatri

Vinay Khatri
Last updated on February 26, 2024

    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:

    Leave a Comment on this Post

    0 Comments