finding minimum number of platforms required if arrival and departure time of trains given in sorted order of arrival time

#include <stdio.h>

typedef struct {

int a, d;
}Train;



int minPlatform(Train a[], int n) {

int platforms[n];

int i, j;
int num = 1;

platforms[0] = a[i].d; //time when plaform 0 will be free

for(i = 1; i < n; ++i) {

for(j = 0; j < num; ++j) {

if(platforms[j] < a[i].a) { //arrival time is after freeing the platform

platforms[j] = a[i].d; //assign platform j to train i

break;
}
}

if(j == num) { //all platforms busy
platforms[num] = a[i].d; //allocate one more platform
num++;
}

}


return num;
}


int main() {


Train a[] = {{1, 10}, {9, 13}, {10, 15}, {17,20}, {20, 22}, {24, 25}};


printf("%d\n", minPlatform(a, sizeof(a)/sizeof(Train)));

return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s