## Introduction

In this blog, we will discuss how to find the **Minimum Number of Platforms Required for a Railway/Bus Station.** Such problems do come in interviews as well as in many contests. Before solving the problem, it’s recommended to have a good understanding of sortings and its applications. In this Blog we will dive deep into each detail to get a firm hold over the application of sorting in problems.

Let’s look at the problem statement.

Given a list of arrival and departure times of trains that reach a railway station. The task is to find the minimum number of railway platforms required such that no train waits.

Let’s understand the problem using an example.

** Input: ** N and arrival and departure times of length N,

**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

** Explanation: **The minimum number of railway platforms needed is 3 because the maximum number of trains is 3 from 11:00 to 11:20.

## Approach(Naive)

First, let’s look at the naive approach that would probably strike anybody’s mind before jumping to an optimal approach.

So, the basic approach is to start from each index and find the number of overlapping intervals. We can maximize this value by computing the number of overlapping intervals from each index and updating it in each iteration.

So the naive/basic approach could be formulated as:

- For each index, compute the number of overlapping intervals.
- Keep updating the maximum value in each iteration.
- Finally, return the maximum value.

Now let’s look at the PseudoCode.

### PseudoCode

**Algorithm**

___________________________________________________________________

**procedure** findMinimumPlatforms(arr, dep, N):

___________________________________________________________________

**1.** minPlatforms ← 1 **#initially the maximum number of platforms needed is 1.**

**2. for** time_i = 0 **to** N-1 **do** **# from every time at index i **

**3.** ** **platforms_needed ←** **1 **# for each index min platform is at least 1.**

**4. for **time_j = time_i+1 **to** N-1 **do **

**5.** **if** overlap(arr[time_i], dep[time_i], arr[time_j], dep[time_j]) **== **True **do**

**6. ** ** **platforms_needed ← platforms_needed + 1

**7. end if**

**8. end for**

**9. **minPlatforms ← max(minPlatforms, platforms_needed)

**10. end for**

**11. return **minPlatforms

**12**. **end procedure**

___________________________________________________________________

### CODE IN C++

```
//C++ program to find the minimum number of platforms needed
#include <bits/stdc++.h>
using namespace std;
// function which returns a boolean value if 2 intervals overlap or not
bool overlap(int arr_i, int dep_i, int arr_j, int dep_j) {
return (arr_i >= arr_j and arr_i <= dep_j) or (arr_j >= arr_i and arr_j <= dep_i);
}
// function that returns minimum number of platforms Needed
int minPlatformsNeeded(vector<int> &arr, vector<int> &dep, int N) {
int minPlatforms = 0; // minimum number of platforms
// from each index find the number of platforms_needed
for (int i = 0; i < N - 1; ++i) {
int platforms_needed = 1; // at least one platform is needed
for (int j = i + 1; j < N; ++j) {
// if the time intervals overlap increment the number of platforms needed
if (overlap(arr[i], dep[i], arr[j], dep[j]))
platforms_needed++;
}
minPlatforms = max(minPlatforms, platforms_needed);
}
return minPlatforms;
}
int main() {
// The number of arrivals and departures
int N = 6;
// The arrival time stamps
vector<int> arr{900, 940, 950, 1100, 1500, 1800};
// The departure time stamps
vector<int> dep{910, 1200, 1120, 1130, 1900, 2000};
cout << "The minimum number of platforms needed are/is: ";
cout << minPlatformsNeeded(arr, dep, N) << '\n';
return 0;
}
```

**Output**

`The minimum number of platforms needed are/is: 3`

### Complexity Analysis

**Time Complexity:** O(n^{2})

This is because we iterate through all indices for each index. Hence it’s O(n^{2}).

**Space complexity**: O(1) at the worst case because no extra space is used.

The above algorithm works in O(n^{2}) time which is pretty slow. This gives us the motivation to improve our algorithm.

So let’s think about an efficient approach to solve the problem.