Question
Given schedule of n trains with respective arrival and stoppage time at a Railway Station, find minimum number of platforms needed.
The complete question can be found here.
Solution by Nikhil Mohan.
Algorithm
|
Sort the arrival and departure time of trains. |
|
|
Create two pointers i=0, and j=0 and a variable to store ans and current count plat |
|
|
Run a loop while i<n and j<n and compare the ith element of arrival array and jth element of departure array. |
|
|
if the arrival time is less than or equal to departure then one more platform is needed so increase the count, i.e. plat++ and increment i |
|
|
Else if the arrival time greater than departure then one less platform is needed so decrease the count, i.e. plat++ and increment j |
|
|
Update the ans, i.e ans = max(ans, plat). |
|
Implementation: This doesn’t create a single sorted list of all events, rather it individually sorts arr[] and dep[] arrays, and then uses merge process of merge sort to process them together as a single sorted array.
Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int solve(ll a[],ll b[],int n)
{
sort(a,a+n);
sort(b,b+n);
int p=1,result=1;
for(int i=1,j=0; i<n && j<n;)
{
if (a[i]<=b[j])
{p++;
i++;}
else if (a[i]>b[j])
{ p--;
j++;}
result=max(result,p);
}
return result;
}
void test()
{
ll n;
scanf("%lld",&n);
ll a[n];
ll b[n];
ll s,t;
for(int i=0;i<n;i++)
{scanf("%lld%lld",&s,&t);
a[i]=s;
b[i]=s+t;
}
cout<<solve(a,b,n);
}
int main()
{
test();
}