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 RohitOberoi

**Output:**

`Minimum number of platforms required = 3`

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

**Output**:

`Minimum number of platforms required = 3`

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above through **WhatsApp** me.