# Find Minimum Platforms Needed to Avoid Delay in the Train Arrival

Posted in

Vinay Khatri
Last updated on September 21, 2024

## Problem

The objective is to identify the minimal number of train platforms necessary for the railway station, as all trains arriving and departing reach the railway station. We have two arrays that show trains that cease arriving and departing time.

#### Sample Input

```Trains arrival   = { 200, 210, 300, 320, 350, 500 }
Trains departure = { 230, 340, 320, 430, 400, 520 }```

`2`

## Approach

The goal is to take all occurrences into account in sequence. Once the event is sorted, track the number of trains that have arrived but have not gone at any moment. Sort train timings of arrival and departure.

Create two variables ``` i ``` ``` =0 ``` and ``` j ``` ``` =0 ``` and a ``` plat ``` variable with the current count platform. Run a loop while ``` i < n ``` and ``` j < n ``` and compare the array's ``` ith ``` element to the ``` jth ``` departure element. If the time of arrival is less than or equal to the start, then another platform is needed, such that the number of platforms increases, i.e. ``` plat+ ``` ``` + ``` and ``` i ``` increases.

If the time of arrival exceeds the departure, fewer platforms are necessary so that the number of platforms decreases and increase j. Update answer, i.e., = ``` max (ans, plat) ``` .

### Python Programming

```def findPlatform(arrival, departure, n):

# Sort arrival and
# departure arrays
arrival.sort()
departure.sort()
plat = 1
ans = 1
i = 1
j = 0

while (i < n and j < n):

# If next event in sorted
# order is arrival,
# increment count of
# platforms
if (arrival[i] <= departure[j]):

plat += 1
i += 1

elif (arrival[i] > departure[j]):

plat -= 1
j += 1

if (plat > ans):
ans = plat

return ans

arrival = [900, 940, 950, 1100, 1500, 1800]
departure = [910, 1200, 1120, 1130, 1900, 2000]
n = len(arrival)

print("Minimum Number = ",
findPlatform(arrival, departure, n))```

Output

`Minimum Number = 3`

### C++ Programming

```#include <algorithm>
#include <iostream>
using namespace std;
int solve(int arrival[], int departure[], int n)
{

// Sort arrival and departure arrays
sort(arrival, arrival + n);
sort(departure, departure + n);
int plat = 1, ans = 1;
int i = 1, j = 0;
while (i < n && j < n) {

// If next event in sorted order is arrival,
// increment count of platforms needed

if (arrival[i] <= departure[j]) {
plat++;
i++;
}

// Else decrement
else if (arrival[i] > departure[j]) {
plat--;
j++;
}

// update ans
if (plat > ans)
ans = plat;
}
return ans;
}
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 = "
<< solve(arrival, departure, n);
return 0;
}```

Output

`Minimum number = 3`

### C# Programming

```using System;

class Solution {
static int solve(int[] arrival, int[] departure, int n)
{
Array.Sort(arrival);
Array.Sort(departure);
int plat = 1, ans = 1;
int i = 1, j = 0;

while (i < n && j < n) {
// If next event in sorted order
// is arrival, increment count
// of platforms
if (arrival[i] <= departure[j])
{
plat++;
i++;
}
// Else decrement
else if (arrival[i] > departure[j])
{
plat--;
j++;
}

// Update ans if needed
if (plat > ans)
ans = plat;
}
return ans;
}

public static void Main()
{
int[] arrival = { 900, 940, 950, 1100, 1500, 1800 };
int[] departure = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = arrival.Length;

Console.Write("Minimum number = "
+ solve(arrival, departure, n));
}

}```

Output

`Minimum number = 3`