Minimum Number of Platforms Required for a Railway/Bus Station | Set 2 (Set based approach)
Last Updated :
16 Jul, 2024
Given the arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train waits. We are given two arrays that represent arrival and departure times of trains that stop.
Examples:
Input: arr[] = {0900, 0940, 0950, 1100, 1500, 1800}, dep[] = {0910, 1200, 1120, 1130, 1900, 2000}
Output: 3
Explanation: There are at-most three trains at a time (time between 11:00 to 11:20).
Input: arr[] = {0900, 1235, 1100}, dep[] = {1000, 1240, 1200}
Output: 1
Explanation: All train times are mutually exclusive. So we need only one platform.
Approach: To solve the problem, follow the below idea:
The problem can be solved using a multiset. We can insert all the arrival and departure times in a multiset in the form of pairs, where the first value of the pair tells the arrival/departure time and second value tells whether it's arrival or departure represented by 'a' or 'd' respectively.
We can maintain a variable, say occupiedPlatforms to keep track of the platforms currently in use. Now, we can iterate over the multiset and for each element, check if its arrival time or departure time.
- If the next time is an arrival time, then we increment occupiedPlatforms by 1 as we need more platforms on arrival of a train.
- If the next time is a departure time, then we decrement occupiedPlatforms by 1 as one platform has become empty on departure of a train.
The maximum value of occupiedPlatforms at any point is the minimum number of platforms required.
Below is the implementation of the above approach:
C++
// C++ program to find minimum number of platforms
// required on a railway station
#include <bits/stdc++.h>
using namespace std;
int findPlatform(int arr[], int dep[], int n)
{
// Insert all the times (arr. and dep.)
// in the multiset.
multiset<pair<int, char> > order;
for (int i = 0; i < n; i++) {
// If its arrival then second value
// of pair is 'a' else 'd'
order.insert(make_pair(arr[i], 'a'));
order.insert(make_pair(dep[i], 'd'));
}
int result = 0;
int occupiedPlatforms = 0;
// Start iterating the multiset.
for (auto it : order) {
// If its 'a' then add 1 to occupiedPlatforms
// else minus 1 from occupiedPlatforms.
if (it.second == 'a')
occupiedPlatforms++;
else
occupiedPlatforms--;
if (occupiedPlatforms > result)
result = occupiedPlatforms;
}
return result;
}
// Driver code
int main()
{
int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum Number of Platforms Required = "
<< findPlatform(arr, dep, n);
return 0;
}
// Java program to find minimum number
// of platforms required on a railway station
import java.io.*;
import java.util.*;
class pair {
int first;
char second;
pair(int key1, char key2)
{
this.first = key1;
this.second = key2;
}
}
class GFG {
public static int findPlatform(int arr[], int dep[],
int n)
{
// Insert all the times (arr. and dep.)
// in the ArrayList of pairs.
ArrayList<pair> order = new ArrayList<>();
for (int i = 0; i < n; i++) {
order.add(new pair(arr[i], 'a'));
order.add(new pair(dep[i], 'd'));
}
// Custom sort order ArrayList, first
// by time than by arrival or departure
Collections.sort(order, new Comparator<pair>() {
public int compare(pair p1, pair p2)
{
if (p1.first == p2.first)
return new Character(p1.second)
.compareTo(
new Character(p2.second));
return p1.first - p2.first;
}
});
int result = 1;
int occupiedPlatforms = 0;
for (int i = 0; i < order.size(); i++) {
pair p = order.get(i);
// If its 'a' then add 1 to occupiedPlatforms
// else minus 1 from occupiedPlatforms.
if (p.second == 'a')
occupiedPlatforms++;
else
occupiedPlatforms--;
if (occupiedPlatforms > result)
result = occupiedPlatforms;
}
return result;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = 6;
System.out.println("Minimum Number of "
+ "Platforms Required = "
+ findPlatform(arr, dep, n));
}
}
# Python3 program to find minimum number
# of platforms required on a railway station
def findPlatform(arr, dep, n):
# Inserting all the arr. and dep. times
# in the array times
times = []
for i in range(n):
times.append([dep[i], 'd'])
times.append([arr[i], 'a'])
# Sort the array
times = sorted(times, key = lambda x: x[1])
times = sorted(times, key = lambda x: x[0])
result, occupiedPlatforms = 0, 0
for i in range(2 * n):
# If its 'a' then add 1 to occupiedPlatforms
# else minus 1 from occupiedPlatforms.
if times[i][1] == 'a':
occupiedPlatforms += 1
result = max(occupiedPlatforms, result)
else:
occupiedPlatforms -= 1
return result
# Driver code
arr = [ 900, 940, 950, 1100, 1500, 1800 ]
dep = [ 910, 1200, 1120, 1130, 1900, 2000 ]
n = len(arr)
print("Minimum Number of Platforms Required =",
findPlatform(arr, dep, n))
// C# program to find minimum number
// of platforms required on a railway station
using System;
using System.Collections.Generic;
public class pair {
public int first;
public char second;
public pair(int key1, char key2) {
this.first = key1;
this.second = key2;
}
}
public class GFG {
public static int findPlatform(int []arr, int []dep, int n) {
// Insert all the times (arr. and dep.)
// in the List of pairs.
List<pair> order = new List<pair>();
for (int i = 0; i < n; i++) {
order.Add(new pair(arr[i], 'a'));
order.Add(new pair(dep[i], 'd'));
}
// Custom sort order List, first
// by time than by arrival or departure
order.Sort((p1,p2)=> p1.first == p2.first? p1.second -
p2.second: p1.first - p2.first);
int result = 1;
int occupiedPlatforms = 0;
for (int i = 0; i < order.Count; i++) {
pair p = order[i];
// If its 'a' then add 1 to occupiedPlatforms
// else minus 1 from occupiedPlatforms.
if (p.second == 'a')
occupiedPlatforms++;
else
occupiedPlatforms--;
if (occupiedPlatforms > result)
result = occupiedPlatforms;
}
return result;
}
// Driver Code
public static void Main(String[] args) {
int []arr = { 900, 940, 950, 1100, 1500, 1800 };
int []dep = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = 6;
Console.WriteLine("Minimum Number of " +
"Platforms Required = " +
findPlatform(arr, dep, n));
}
}
// JavaScript program to find minimum number of platforms required on a railway station
const findPlatform = (arr, dep, n) => {
// Insert all the times (arr. and dep.)
// in the multiset.
let order = new Set();
for (let i = 0; i < n; i++) {
// If its arrival then second value
// of pair is 'a' else 'd'
order.add([arr[i], 'a']);
order.add([dep[i], 'd']);
}
let result = 0;
let occupiedPlatforms = 0;
order = [...order];
order = order.sort((a, b) => a[0] - b[0])
// Start iterating the multiset.
for (let it in order) {
// If its 'a' then add 1 to occupiedPlatforms
// else minus 1 from occupiedPlatforms.
if (order[it][1] == 'a')
occupiedPlatforms++;
else
occupiedPlatforms--;
if (occupiedPlatforms > result)
result = occupiedPlatforms;
}
return result;
}
// Driver code
let arr = [900, 940, 950, 1100, 1500, 1800];
let dep = [910, 1200, 1120, 1130, 1900, 2000];
let n = arr.length;
console.log(`Minimum Number of Platforms Required = ${findPlatform(arr, dep, n)}`);
OutputMinimum Number of Platforms Required = 3
Time Complexity: O(N* LogN), Since we are inserting into multiset and it maintain elements in sorted order. So N insert operations in multiset requires N*LogN time complexity.
Auxiliary Space: O(N), we are using multiset which will have 2*N elements.
Related Article: Minimum Number of Platforms Required for a Railway/Bus Station
Similar Reads
Computer Science Subjects