NPTEL (WEEK-7.2)

Programming Assignment 7.2: Number of railway platforms

Due on 2016-03-10, 23:55 IST

At a railway station, we have time-table of trains arrival and departure. We need to find the minimum number of platforms so that all the trains can be accommodated as per their schedule.

Consider the time to be 24 hours format

Input:

First line contain integer n denoting the number of trains

Second line contains the arrival time of trains (separated by spaces)

Third line contains the departure time of trains

Output:

Minimum number of platforms so that all the trains are accommodated

n

a1 a2   … an

b1 b2   … bn

Example:

Input:

3

1 2 5

4 7 9

Output:

2

Constrains

1<n<10

0000 <= ai <=2400

0000 <= bi <=2400

PROGRAM:

#include<cstdio>

#include<cstdlib>

using namespace std;

/*

* @ Find the number of platforms required for accommodating the trains

* @ Input : arr   : array of arrival times

*      dep : array of departure times

*      n   : number of trains

*    return the minimum number of platforms

*/

int findPlatform(int arr[], int dep[], int n);

int cmpfunc (const void * a, const void * b)

{

   return ( *(int*)a - *(int*)b );

}

int main(){

int n,count,i;

scanf("%d",&n);

int * arr = (int*) malloc(n*sizeof(int));

int * dep = (int*) malloc(n*sizeof(int));

for(i=0;i<n;i++)

scanf("%d",&arr[i]);

  for(i=0;i<n;i++)

scanf("%d",&dep[i]);

        printf("%d",findPlatform(arr, dep, n));

return 0;

}

 CODING:

int findPlatform(int arr[], int dep[], int n){ int result = 1,ii=0,j=0,a; //TODO // Sort arrival and departure arrays //sort(arr, arr+n); for (ii = 0; ii < n; ++ii) { for (j = ii + 1; j < n; ++j) { if (arr[ii] > arr[j]) { a = arr[ii]; arr[ii] = arr[j]; arr[j] = a; } } } //sort(dep, dep+n); for (ii= 0; ii < n; ++ii) { for (j = ii + 1; j < n; ++j) { if (dep[ii] > dep[j]) { a = dep[ii]; dep[ii] = dep[j]; dep[j] = a; } } } // plat_needed indicates number of platforms needed at a time int plat_needed = 1; int i = 1; j = 0; // Similar to merge in merge sort to process all events in sorted order while (i < n && j < n) { // If next event in sorted order is arrival, increment count of // platforms needed if (arr[i] < dep[j]) { plat_needed++; i++; if (plat_needed > result) // Update result if needed result = plat_needed; } else // Else decrement count of platforms needed { plat_needed--; j++; } } return result; }