Search⌘ K
Home
Courses
Algorithms for Coding Interviews in C++

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

Explore how to determine the minimum number of platforms required at a train station by reviewing three solutions: a brute force approach, a sorting-based optimization, and an efficient map-based solution using C++ multimaps. Understand their time complexities and how to implement greedy algorithms for interval overlap problems.

We'll cover the following...

Solution #1: Brute Force

C++
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) ...