Railway Station
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 <= N <= 10^5
0 <= a <= 86400
0 < b <= 86400
Number of platforms > 0
Input
First line contains N denoting number of trains.
Next N line contain 2 integers, a and b, denoting the arrival time and stoppage time of train.
Output
Single integer denoting the minimum numbers of platforms needed to accommodate every train.
Example 1
Input
3
10 2
5 10
13 5
Output
2
Explanation
The earliest arriving train at time t = 5 will arrive at platform# 1. Since it will stay there till t = 15, train arriving at time t = 10 will arrive at platform# 2. Since it will depart at time t = 12, train arriving at time t = 13 will arrive at platform# 2.
Example 2
Input
2
2 4
6 2
Output
2
Explanation
Platform #1 can accommodate train 1.
Platform #2 can accommodate train 2.
Note that the departure of train 1 is same as arrival of train 2, i.e. 6, and thus we need a separate platform to accommodate train 2.
Program:
#include<stdio.h>
#include<math.h>
int main()
{
int n,swap=0;
scanf("%d",&n);
int a[n],b[n];
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
scanf("%d",&b[i]);
b[i]=a[i]+b[i];
}
for (int c = 0 ; c < n ; c++)
{
for ( int d = 0 ; d < n - c - 1; d++)
{
if (a[d] > a[d+1]) /* For decreasing order use '<' instead of '>' */
{
swap = a[d];
a[d] = a[d+1];
a[d+1] = swap;
}
}
}
for (int c = 0 ; c < n ; c++)
{
for ( int d = 0 ; d < n - c - 1; d++)
{
if (b[d] > b[d+1]) /* For decreasing order use '<' instead of '>' */
{
swap = b[d];
b[d] = b[d+1];
b[d+1] = swap;
}
}
}
int p=1,r=1,i=1,j=0;
while(i<n && j<n)
{
if(a[i]<=b[j])
{
p++;
i++;
}
else if(a[i]>b[j])
{
p--;
j++;
}
if(p>r)
r=p;
}
printf("%d",r);
}
No comments:
Post a Comment