...

/

Solution: Find Minimum Number of Platforms Required for a Train Station

Solution: Find Minimum Number of Platforms Required for a Train Station

This review provides a detailed analysis of the solutions to find the number of platforms required for a train station.

Solution #1: Brute Force

Press + to interact
int findPlatform(int arrival[], int departure[], int n) {
int result = 0;
int count = 0;
for (int index = 0; index < n; index++){
count = 0;
for (int i = 1; i < n; i++){
if(arrival[i] >= arrival[index] && arrival[i] <= departure[index]) {
count++;
}
}
if (result < count)
result = count;
}
return result;
}
int main() {
int arrival[] = {900, 940, 950, 1100, 1500, 1800};
int departure[] = {910, 1200, 1120, 1130, 1900, 2000};
int n = sizeof(arrival) / sizeof(arrival[0]);
cout << "Minimum Number of Platforms Required for Plan1 = " <<
findPlatform(arrival, departure, n);
cout << endl << endl;
// Example 2
int arrival1[] = {200, 210, 300, 320, 350, 500};
int departure1[] = {230, 240, 320, 430, 400, 520};
int n1 = sizeof(arrival1) / sizeof(arrival1[0]);
cout << "Minimum Number of Platforms Required for Plan2 = " <<
findPlatform(arrival1, departure1, n1);
return 0;
}

The problem is to find the maximum number of trains that are there on the given railway station at a time. An Iterative solution would be to take every interval one by one and find the number of intervals that overlap with it. Keep track of the maximum number of intervals that overlap with an interval and then return the maximum value.

Time Complexity

Since this algorithm moves iteratively, the time complexity will be O(n2)O(n^2) ...

Access this course and 1400+ top-rated courses and projects.