Skip to main content

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:

Labels: