Given arrival and departure times of all
trains that reach a railway station, find the minimum number of platforms
required for the railway station so that no train waits.
Input
Format:
The first line of input consists of an
integer N that represents total number of trains.
The next N lines contain arrival Ta[i] and
departure Td[i] time for each train. Time will be given in 24H format and
colons will be omitted for convenience. For ex.: 9:05AM will be given as
"905", or 9:10PM will be given as "2110".
Constrains:
0 < N < 1000
0000 < T[a] < T[d] < 2359
Output
Format:
Output integer value of the minimum
required platforms.
Sample
Input:
3
900 920
910 950
940 1000
Sample
Output:
2
Explanation:
We need 2 platforms for #1 and #2 trains.
#3 train can use same platform as #1 train, since #1 train will depart by that
time
Solution:
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int i,n;
cin>>n;
int a[n],d[n];
for(i=0;i<n;i++)
cin>>a[i]>>d[i];
sort(a,a+n);
sort(d,d+n);
int x=1,y=0,p=1,m=1;
while(x<n&&y<n)
{
if(a[x]<d[y])
{
p++;
x++;
m=max(p,m);
}
else
{
y++;
p--;
}
}
cout<<m;
return 0;
}