Minimum Platforms

Task: Find the number platforms required to a railway station, by the list of trains arrival and departure times, with those platforms no train need not to be wait.

Example:

Input:

3

0900 1100 1235

1000 1200 1240

Output:

1

---

Here is the Code:

Program in C++:

1. #include<iostream>
2. #include<bits/stdc++.h>
3. using namespace std;
4. int minimumPlatforms(int *a,int *d,int n)
5. {
6.     multimap<int,int> m;
7.     for(int i=0;i<n;i++)
8.     {
9.         m.insert({a[i],d[i]});
10.     }
11.     int k=0;
12.     for(auto i=m.begin();i!=m.end();i++)
13.     {
14.         a[k]=i->first;
15.         d[k]=i->second;
16.         k++;
17.     }
18.     /*sort(a,a+n);
19.     sort(d,d+n);* Execution Time : 0.11 */
20.     int pf=1,c,j;
21.     for(int i=1;i<n;i++)
22.     {
23.         j=0,c=1;
24.         while(j<i)
25.         {
26.             if(a[j]<=a[i]&&a[i]<=d[j]) c++;
27.             j++;
28.         }
29.         if(pf<c) pf = c;
30.     }
31.     return pf;
32. }
33. int main()
34.  {
35. int t;
36. cin>>t;
37. while(t--)
38. {
39.     int n;
40.     cin>>n;
41.     int a[n],d[n];
42.     for(int i=0;i<n;i++)
43.     {
44.         cin>>a[i];
45.     }
46.     for(int j=0;j<n;j++)
47.     {
48.         cin>>d[j];
49.     }
50.     cout<<minimumPlatforms(a,d,n)<<endl;
51. }
52. return 0;
53. }

---

Here is the Video: