Here another time to calculate the Minimum Number of Platforms Required for a Railway Station by Map based approach, So, the arrival and departure times of all trains arriving at the railway station, So, find the minimum number of platforms required for the railway station, so that no trains wait. We are given two arrays that represent the arrival and departure times of the stopped trains.
Examples:
Input: 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
There are at-most three trains at a time
(time between 11:00 to 11:20)In this post, again we are solving this problem by inserting all the arrival and departure times in a multimap.
The first value of the element in multimap tells the arrival/departure time and the second value tells whether it’s arrival or departure represented by ‘a’ or ‘d’ respectively.
If it’s arrival then do increment by 1 otherwise decrease the value by 1. If we are taking the input from STDIN then we can directly insert the times in the multimap and no need to store the times in the array.
C++ program to find the minimum number of platforms required on a railway station
// 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 multimap.
multimap<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 plat_needed = 0;
multimap<int, char>::iterator it = order.begin();
// Start iterating the multimap.
for (; it != order.end(); it++) {
// If its 'a' then add 1 to plat_needed
// else minus 1 from plat_needed.
if ((*it).second == 'a')
plat_needed++;
else
plat_needed--;
if (plat_needed > result)
result = plat_needed;
}
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 the minimum number of platforms required on a railway station
// 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 plat_needed = 0;
for(int i = 0; i < order.size(); i++)
{
pair p = order.get(i);
// If its 'a' then add 1 to plat_needed
// else minus 1 from plat_needed.
if (p.second == 'a')
plat_needed++;
else
plat_needed--;
if (plat_needed > result)
result = plat_needed;
}
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));
}
}
// This code is contributed by RohitOberoiOutput:
Minimum number of platforms required = 3Another Method:
Suppose if all the arrival and departure occurs on the same day then we can use auxiliary array to compute the required number of the platform in O(n).
Means whenever an arrival occurs we increase the count of the required platform when a departure occurs we decrease the required platform at same point of time.
We take the cumulative sum which would provide the required number of platform for all point of time out of these values maximum value is our answer.
// C++ program to find minimum number of platforms
// required on a railway station
#include <bits/stdc++.h>
using namespace std;
int minPlatform(int arrival[], int departure[], int n)
{
// as time range from 0 to 2359 in 24 hour clock,
// we declare an array for values from 0 to 2360
int platform[2361] = {0};
int requiredPlatform = 1;
for (int i = 0; i < n; i++) {
// increment the platforms for arrival
++platform[arrival[i]];
// once train departs we decrease the platform count
--platform[departure[i] + 1];
}
// We are running loop till 2361 because maximum time value
// in a day can be 23:60
for (int i = 1; i < 2361; i++) {
// taking cumulative sum of platform give us required
// number of platform fro every minute
platform[i] = platform[i] + platform[i - 1];
requiredPlatform = max(requiredPlatform, platform[i]);
}
return requiredPlatform;
}
// 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 = "
<< minPlatform(arr, dep, n);
return 0;
}// Java program to find minimum number
// of platforms required on a railway
// station
import java.util.*;
import java.lang.*;
class GFG{
static int minPlatform(int arrival[],
int departure[],
int n)
{
// As time range from 0 to 2359 in
// 24 hour clock, we declare an array
// for values from 0 to 2360
int[] platform = new int[2361];
int requiredPlatform = 1;
for(int i = 0; i < n; i++)
{
// Increment the platforms for arrival
++platform[arrival[i]];
// Once train departs we decrease
// the platform count
--platform[departure[i] + 1];
}
// We are running loop till 2361 because
// maximum time value in a day can be 23:60
for(int i = 1; i < 2361; i++)
{
// Taking cumulative sum of platform
// give us required number of
// platform fro every minute
platform[i] = platform[i] +
platform[i - 1];
requiredPlatform = Math.max(requiredPlatform,
platform[i]);
}
return requiredPlatform;
}
// 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 = arr.length;
System.out.println("Minimum Number of " +
"Platforms Required = " +
minPlatform(arr, dep, n));
}
}
// This code is contributed by offbeat# Python3 program to find minimum number
# of platforms required on a railway station
def minPlatform(arrival, departure, n):
# As time range from 0 to 2359 in
# 24 hour clock, we declare an array
# for values from 0 to 2360
platform = [0] * 2631
requiredPlatform = 1
for i in range(n):
# Increment the platforms for arrival
platform[arrival[i]] += 1
# Once train departs we decrease the
# platform count
platform[departure[i] + 1] -= 1
# We are running loop till 2361 because
# maximum time value in a day can be 23:60
for i in range(1, 2631):
# Taking cumulative sum of
# platform give us required
# number of platform fro every minute
platform[i] = platform[i] + platform[i - 1]
requiredPlatform = max(requiredPlatform,
platform[i])
return requiredPlatform
# 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 = ",
minPlatform(arr, dep, n))
# This code is contributed by PawanJain1Output:
Minimum number of platforms required = 3Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above through WhatsApp me.
