Question

Given schedule of trains and their stoppage time at a Railway Station, find minimum number of platforms needed. Note - If Train A's departure time is x and Train B's arrival time is x, then we can't accommodate Train B on the same platform as Train A. - Constraints 1 0 · Input First line contains N denoting number of trains. time and stoppage time of train.​

Answer 1

Answer:

#include <bits/stdc++.h>

 using namespace std;

int main()

{

int n;

scanf("%d",&n);

  int ari[n],stop[n],both[n],i,j=0,max=1,d;

    for(i=0;i<n;i++)

    {

     scanf("%d",&ari[i]);

     scanf("%d",&stop[i]);

     both[i]=ari[i]+stop[i];

 }

 sort(ari,ari+n);

 sort(both,both+n);

 d=max;

  for(i=1;i<n;i++)

  {

   if(ari[i]<=both[j])

   {

    d++;

   }

   else

   {

    d--;

    i=i-1;

    j++;

   }

   if(d>max)

   max=d;

  }

  printf("%d",max);

}

Explanation:

keep the count of number of trains arriving and leaving in d...maximum value of d is the no of platforms required.

first sort the array of arrival time and array having sum of arrival and stopping time.

Now start from the array of arrival time...if the number in the both array is less than the arrival time array then a train leaves so a new train can stop there,so decrease the value of d(d implies no of trains are present at this moment).so max value of d gives no of platforms required.