The Interview Question Today#6(1-3-19)

Question:

The algorithm to find the minimum number of platforms required for the railway station so that no train waits according to arrival and departure time

Example:

Input:  arr[]  = {9:00,  9:40, 9:50,  11:00, 15:00, 18:00}

           dep[]  = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}

Output: 3

Approach:

1. Sort both arrival(arr) and departure(dep) arrays.
2. Compare the current element in arrival and departure array and pick smaller one among both.
3. If the element is pick up from arrival array then increment platform_needed.
4. If the element is pick up from departure array then decrement platform_needed.
5. While performing the above steps, we need a track count of maximum value reached for platform_needed.
6. In the end, we will return the maximum value reached for platform_needed.

C program:

#include<stdio.h>

    void main()

{

int arr[100];

int dep[100];

int n=1,i=0;

while(n!=0){

printf("Enter the train arrival & departure time(format-:12:30=1230 in 24 hrs scale\n");

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

        i++;

        printf("Enter zero if all train information is feed \n ");

        scanf("%d",&n);

}

printf("Minimum platforms needed:%d",findPlatformsRequiredForStation(arr,dep,i-1));

}

int findPlatformsRequiredForStation(int arr[], int dep[], int n)

{

int platform_needed = 0, maxPlatforms = 0;

int k,m;

double swap;

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

    {

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

        {

            if(arr[k]<arr[m])

            {

                swap=arr[k];

                arr[k]=arr[m];

                arr[m]=swap;

            }

        }

    }

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

    {

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

        {

            if(dep[k]<dep[m])

            {

                swap=dep[k];

                dep[k]=dep[m];

                dep[m]=swap;

            }

        }

    }

     int i = 0, j = 0;

while (i < n && j < n)

{

if (arr[i] < dep[j])

{

platform_needed++;

i++;

if (platform_needed > maxPlatforms)

maxPlatforms = platform_needed;

}

else

{

platform_needed--;

j++;

}

}

return maxPlatforms;

}

Output:

Enter the train arrival & departure time(format-:12:30=1230 in 24 hrs scale

200

230

Enter zero if all train information is feed

 210

Enter the train arrival & departure time(format-:12:30=1230 in 24 hrs scale

210

320

Enter zero if all train information is feed

 1

Enter the train arrival & departure time(format-:12:30=1230 in 24 hrs scale

300

340

Enter zero if all train information is feed

 1

Enter the train arrival & departure time(format-:12:30=1230 in 24 hrs scale

320

400

Enter zero if all train information is feed

 3

Enter the train arrival & departure time(format-:12:30=1230 in 24 hrs scale

350

430

Enter zero if all train information is feed

 5

Enter the train arrival & departure time(format-:12:30=1230 in 24 hrs scale

500

520

Enter zero if all train information is feed

 0

Minimum platforms needed:2