Given the arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits. We are given two arrays that represent the arrival and departure times of trains that stop.
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
Explanation: There are at-most three trains at a time (time between 9:40 to 12:00)Input: arr[] = {9:00, 9:40}, dep[] = {9:10, 12:00}
Output: 1
Explanation: Only one platform is needed.
Naive Approach:
The idea is to take every interval one by one and find the number of intervals that overlap with it. Keep track of the maximum number of intervals that overlap with an interval. Finally, return the maximum value.
Illustration:
Follow the steps mentioned below:
- Run two nested loops from start to end.
- For every iteration of the outer loop, find the count of intervals that intersect with the current interval except itself.
- Update the answer with the maximum count of overlap in each iteration of the outer loop.
- Print the answer.
Below is the implementation of the above approach:
C
// C program to find minimum number of platforms required on// a railway station// Importing the required header files#include <stdio.h>// Creating MACRO for finding the maximum number#define max(x, y) (((x) > (y)) ? (x) : (y))// Function to find the minimum number of platforms// requiredint findPlatform(int arr[], int dep[], int n){ // plat_needed indicates number of platforms // needed at a time int plat_needed = 1, result = 1; // Run a nested for-loop to find the overlap for (int i = 0; i < n; i++) { // Initially one platform is needed plat_needed = 1; for (int j = 0; j < n; j++) { if (i != j) // Increment plat_needed when there is an // overlap if (arr[i] >= arr[j] && dep[j] >= arr[i]) plat_needed++; } // Update the result result = max(plat_needed, result); } return result;}// Driver Codeint main(){ // Train 1 => Arrival : 01:00, Departure : 09:00 // Train 2 => Arrival : 03:00, Departure : 04:00 // Train 3 => Arrival : 05:00, Departure : 06:00 int arr[] = { 100, 300, 500 }; int dep[] = { 900, 400, 600 }; int n = sizeof(arr) / sizeof(arr[0]); printf("%d", findPlatform(arr, dep, n)); return 0;} |
C++14
// C++ program to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number of platforms// requiredint findPlatform(int arr[], int dep[], int n){ // plat_needed indicates number of platforms // needed at a time int plat_needed = 1, result = 1; // Run a nested for-loop to find the overlap for (int i = 0; i < n; i++) { // Initially one platform is needed plat_needed = 1; for (int j = 0; j < n; j++) { if (i != j) // Increment plat_needed when there is an // overlap if (arr[i] >= arr[j] && dep[j] >= arr[i]) plat_needed++; } // Update the result result = max(plat_needed, result); } return result;}// Driver Codeint main(){ // Train 1 => Arrival : 01:00, Departure : 09:00 // Train 2 => Arrival : 03:00, Departure : 04:00 // Train 3 => Arrival : 05:00, Departure : 06:00 int arr[] = { 100, 300, 500 }; int dep[] = { 900, 400, 600 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findPlatform(arr, dep, n); return 0;}// Code contributed by farzams101 |
Python3
# Program to find minimum number of platforms# required on a railway stationdef findPlatform(arr, dep, n): ''' Accepts two arrays with arrival and departure time and the size of the array Returns minimum number of platforms required ''' # plat_needed indicates number of platforms # needed at a time plat_needed = 1 result = 1 # run a nested loop to find overlap for i in range(n): # minimum platform needed plat_needed = 1 for j in range(n): # check for overlap if i != j: if (arr[i] >= arr[j] and dep[j] >= arr[i]): plat_needed += 1 # update result result = max(result, plat_needed) return result# Driver codedef main(): arr = [100, 300, 500] dep = [900, 400, 600] n = len(arr) print("{}".format( findPlatform(arr, dep, n)))if __name__ == '__main__': main() |
Java
// Program to find minimum number of platforms// required on a railway stationimport java.io.*;class GFG { // Returns minimum number of platforms required public static int findPlatform(int arr[], int dep[], int n) { // plat_needed indicates number of platforms // needed at a time int plat_needed = 1, result = 1; // run a nested loop to find overlap for (int i = 0; i < n; i++) { // minimum platform plat_needed = 1; for (int j = 0; j < n; j++) { if (i != j) // check for overlap if (arr[i] >= arr[j] && dep[j] >= arr[i]) plat_needed++; } // update result result = Math.max(result, plat_needed); } return result; } // Driver Code public static void main(String[] args) { int arr[] = { 100, 300, 500 }; int dep[] = { 900, 400, 600 }; int n = 3; System.out.println(findPlatform(arr, dep, n)); }} |
Javascript
<script>// Program to find minimum number of platforms// required on a railway stationfunction max(a,b){ if(a==b) return a; else{ if(a>b) return a; else return b; }}// Returns minimum number of platforms requiredfunction findPlatform( arr, dep, n){ // plat_needed indicates number of platforms // needed at a time var plat_needed = 1, result = 1; var i = 1, j = 0; // run a nested loop to find overlap for (var i = 0; i < n; i++) { // minimum platform plat_needed = 1; for (var j = 0; j < n; j++) { // check for overlap if(i != j) if(arr[i] >= arr[j] && dep[j] >= arr[i]) plat_needed++; } // update result result = max(result, plat_needed); } return result;} var arr = [100, 300, 500] var dep = [900, 400, 600] var n = 3; document.write("Minimum Number of Platforms Required = " +findPlatform(arr, dep, n));</script> |
C#
// Program to find minimum number of platforms// required on a railway stationusing System;public class GFG { // Returns minimum number of platforms required public static int findPlatform(int[] arr, int[] dep, int n) { // plat_needed indicates number of platforms // needed at a time int plat_needed = 1, result = 1; int i = 0, j = 0; // run a nested loop to find overlap for (i = 0; i < n; i++) { // minimum platform plat_needed = 1; for (j = 0; j < n; j++) { if (i != j) // check for overlap if (arr[i] >= arr[j] && dep[j] >= arr[i]) plat_needed++; } // update result result = Math.Max(result, plat_needed); } return result; } // Driver Code static public void Main() { int[] arr = { 100, 300, 500 }; int[] dep = { 900, 400, 600 }; int n = 3; Console.WriteLine(findPlatform(arr, dep, n)); }} |
Output
2
Time Complexity: O(n2), Two nested loops traverse the array.
Auxiliary space: O(1), As no extra space is required.
Minimum Number of Platforms Required for a Railway/Bus Station using Heap:
Store the arrival time and departure time and sort them based on arrival time then check if the arrival time of the next train is smaller than the departure time of the previous train if it is smaller then increment the number of the platforms needed otherwise not.
Illustration:
Follow the steps mentioned below:
- Store the arrival time and departure time in array arr and sort this array based on arrival time
- Declare a priority queue(min-heap) and store the departure time of the first train and also declare a counter cnt and initialize it with 1.
- Iterate over arr from 1 to n-1
- check if the arrival time of the current train is less than or equal to the departure time of the previous train which is kept on top of the priority queue
- If true, then push the new departure time and increment the counter cnt
- otherwise, we pop() the departure time
- push new departure time in the priority queue
- check if the arrival time of the current train is less than or equal to the departure time of the previous train which is kept on top of the priority queue
- Finally, return the cnt.
Below is the implementation of the above approach:
C++
// C++ program to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number// of platforms requiredint findPlatform(int arr[], int dep[], int n){ // Store the arrival and departure time vector<pair<int, int> > arr2(n); for (int i = 0; i < n; i++) { arr2[i] = { arr[i], dep[i] }; } // Sort arr2 based on arrival time sort(arr2.begin(), arr2.end()); priority_queue<int, vector<int>, greater<int> > p; int count = 1; p.push(arr2[0].second); for (int i = 1; i < n; i++) { // Check if arrival time of current train // is less than or equals to departure time // of previous train if (p.top() >= arr2[i].first) { count++; } else { p.pop(); } p.push(arr2[i].second); } // Return the number of trains required return count;}// Driver Codeint 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 << findPlatform(arr, dep, n); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.Arrays;import java.util.Comparator;import java.util.PriorityQueue;class GFG { private static class TrainSchedule { int arrivalTime, deptTime; TrainSchedule(int arrivalTime, int deptTime) { this.arrivalTime = arrivalTime; this.deptTime = deptTime; } public String toString() { return "(" + this.arrivalTime + "," + this.deptTime + ")"; } } private static class SortByArrival implements Comparator<TrainSchedule> { @Override public int compare(TrainSchedule o1, TrainSchedule o2) { return o1.arrivalTime - o2.arrivalTime; } } // Function to find the minimum number // of platforms required public static int countPlatforms(int[] arr, int[] dep) { TrainSchedule[] trains = new TrainSchedule[arr.length]; // Store the arrival and departure time for (int i = 0; i < arr.length; i++) { trains[i] = new TrainSchedule(arr[i], dep[i]); } // Sort trains based on arrival time Arrays.sort(trains, new SortByArrival()); PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(trains[0].deptTime); int count = 1; for (int i = 1; i < arr.length; i++) { TrainSchedule curr = trains[i]; // Check if arrival time of current train // is less than or equals to departure time // of previous train if (curr.arrivalTime <= pq.peek()) { count++; } else { pq.poll(); } pq.add(curr.deptTime); } // return the count of number of platforms required return count; } public static void main(String[] args) { int[] arr = { 900, 940, 950, 1100, 1500, 1800 }; int[] dep = { 910, 1200, 1120, 1130, 1900, 2000 }; int res = countPlatforms(arr, dep); System.out.println(res); }} |
Python3
import heapq# Function to find the minimum number# of platforms requireddef findPlatform(arr, dep, n): arr2 = [] # Store the arrival and departure time for i in range(n): arr2.append([arr[i], dep[i]]) arr2.sort() # Sort trains based on arrival time p = [] count = 1 heapq.heappush(p, arr2[0][1]) for i in range(1, n): # Check if arrival time of current train # is less than or equals to departure time # of previous train if p[0] >= arr2[i][0]: count += 1 else: heapq.heappop(p) heapq.heappush(p, arr2[i][1]) # return the count of number of platforms required return countif __name__ == "__main__": arr = [900, 940, 950, 1100, 1500, 1800] dep = [910, 1200, 1120, 1130, 1900, 2000] n = len(arr) print(findPlatform(arr, dep, n)) |
Javascript
// Function to find the minimum number// of platforms requiredfunction findPlatform(arr, dep, n) { // Create an array to store arrival and departure times const arr2 = new Array(n); // Store the arrival and departure time for (let i = 0; i < n; i++) { arr2[i] = { arr: arr[i], dep: dep[i] }; } // Sort the array of arrival and departure times based on the arrival time arr2.sort((a, b) => a.arr - b.arr); // Initialize a priority queue to keep track of the platforms in use const p = []; let count = 1; p.push(arr2[0].dep); // Loop through the array of arrival and departure times for (let i = 1; i < n; i++) { // Check if the next train can use an existing platform if (p[0] <= arr2[i].arr) { // If so, remove the departure time of the previous train from the priority queue p.shift(); } else { // Otherwise, increment the platform count count++; } // Add the departure time of the current train to the priority queue p.push(arr2[i].dep); // Sort the priority queue p.sort(); } // Return the number of platforms required return count;}// Driver Codeconst arr = [900, 940, 950, 1100, 1500, 1800];const dep = [910, 1200, 1120, 1130, 1900, 2000];const n = arr.length;console.log(findPlatform(arr, dep, n)); // Output: 3 |
C#
// C# program to implement the above approachusing System;using System.Collections;using System.Collections.Generic;public class GFG { public class TrainSchedule { public int arrivalTime, deptTime; public TrainSchedule(int arrivalTime, int deptTime) { this.arrivalTime = arrivalTime; this.deptTime = deptTime; } public override string ToString() { return "(" + this.arrivalTime + "," + this.deptTime + ")"; } } // Function to find the minimum number // of platforms required public static int countPlatforms(int[] arr, int[] dep) { TrainSchedule[] trains = new TrainSchedule[arr.Length]; // Store the arrival and departure time for (int i = 0; i < arr.Length; i++) { trains[i] = new TrainSchedule(arr[i], dep[i]); } // Sort trains based on arrival time Array.Sort(trains, (a, b) = > a.arrivalTime - b.arrivalTime); var pq = new Queue<int>(); pq.Enqueue(trains[0].deptTime); int count = 1; for (int i = 1; i < arr.Length; i++) { TrainSchedule curr = trains[i]; // Check if arrival time of current train is // less than or equals to departure time of // previous train if (curr.arrivalTime <= pq.Peek()) { count++; } else { pq.Dequeue(); } pq.Enqueue(curr.deptTime); } // return the count of number of platforms required return count; } // 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 res = countPlatforms(arr, dep); Console.WriteLine(res); }}// This code is contributed by Tapesh(tapeshdua420) |
Output
3
Time Complexity: O(N*log(N)), Heaps take log(n) time for pushing element and there are n elements.
Auxiliary Space: O(N), Space required by heap to store the element.
Minimum Number of Platforms Required for a Railway/Bus Station using Sorting:
The idea is to consider all events in sorted order. Once the events are in sorted order, trace the number of trains at any time keeping track of trains that have arrived, but not departed.
Illustration:
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}All events are sorted by time.
Total platforms at any time can be obtained by subtracting total departures from total arrivals by that time.
Time Event Type Total Platforms Needed at this Time
9:00 Arrival 1
9:10 Departure 0
9:40 Arrival 1
9:50 Arrival 2
11:00 Arrival 3
11:20 Departure 2
11:30 Departure 1
12:00 Departure 0
15:00 Arrival 1
18:00 Arrival 2
19:00 Departure 1
20:00 Departure 0Minimum Platforms needed on railway station = Maximum platforms needed at any time = 3
Note: This doesn’t create a single sorted list of all events, rather it individually sorts arr[] and dep[] arrays, and then uses the merge process of merge sort to process them together as a single sorted array.
Follow the steps mentioned below:
- Sort the arrival and departure times of trains.
- Create two pointers i=1, and j=0, and a variable to store ans and current count plat
- Run a loop while i<n and j<n and compare the ith element of arrival array and jth element of departure array.
- If the arrival time is less than or equal to departure then one more platform is needed so increase the count, i.e., plat++ and increment i
- Else if the arrival time is greater than departure then one less platform is needed to decrease the count, i.e., plat– and increment j
- Update the ans, i.e. ans = max(ans, plat).
Below is the implementation of the above approach:
C
// C program to find minimum number of platforms required on// a railway station// Importing the required header files#include <stdio.h>#include <stdlib.h>// Creating MACRO for finding the maximum number#define max(x, y) (((x) > (y)) ? (x) : (y))// Creating MACRO for finding the minimum number#define min(x, y) (((x) < (y)) ? (x) : (y))// below method is needed for the sort function// compare function, compares two elementsint compare(const void* num1, const void* num2){ if (*(int*)num1 > *(int*)num2) return 1; else return -1;}// Returns minimum number of platforms requiredint findPlatform(int arr[], int dep[], int n){ // Sort arrival and departure arrays qsort(arr, n, sizeof(int), compare); qsort(dep, n, sizeof(int), compare); // plat_needed indicates number of platforms // needed at a time int plat_needed = 1, result = 1; int i = 1, j = 0; // Similar to merge in merge sort to process // all events in sorted order while (i < n && j < n) { // If next event in sorted order is arrival, // increment count of platforms needed if (arr[i] <= dep[j]) { plat_needed++; i++; } // Else decrement count of platforms needed else if (arr[i] > dep[j]) { plat_needed--; j++; } // Update result if needed if (plat_needed > result) result = plat_needed; } return result;}// Driver Codeint main(){ int arr[] = { 900, 940, 950, 1100, 1500, 1800 }; int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 }; int n = sizeof(arr) / sizeof(arr[0]); printf("%d", findPlatform(arr, dep, n)); return 0;} |
C++
// Program to find minimum number of platforms// required on a railway station#include <algorithm>#include <iostream>using namespace std;// Returns minimum number of platforms requiredint findPlatform(int arr[], int dep[], int n){ // Sort arrival and departure arrays sort(arr, arr + n); sort(dep, dep + n); // plat_needed indicates number of platforms // needed at a time int plat_needed = 1, result = 1; int i = 1, j = 0; // Similar to merge in merge sort to process // all events in sorted order while (i < n && j < n) { // If next event in sorted order is arrival, // increment count of platforms needed if (arr[i] <= dep[j]) { plat_needed++; i++; } // Else decrement count of platforms needed else if (arr[i] > dep[j]) { plat_needed--; j++; } // Update result if needed if (plat_needed > result) result = plat_needed; } return result;}// Driver codeint 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 << findPlatform(arr, dep, n); return 0;} |
Java
// Program to find minimum number of platformsimport java.util.*;class GFG { // Returns minimum number of platforms required static int findPlatform(int arr[], int dep[], int n) { // Sort arrival and departure arrays Arrays.sort(arr); Arrays.sort(dep); // plat_needed indicates number of platforms // needed at a time int plat_needed = 1, result = 1; int i = 1, j = 0; // Similar to merge in merge sort to process // all events in sorted order while (i < n && j < n) { // If next event in sorted order is arrival, // increment count of platforms needed if (arr[i] <= dep[j]) { plat_needed++; i++; } // Else decrement count of platforms needed else if (arr[i] > dep[j]) { plat_needed--; j++; } // Update result if 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 = arr.length; 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# Returns minimum number# of platforms requireddef findPlatform(arr, dep, n): # Sort arrival and # departure arrays arr.sort() dep.sort() # plat_needed indicates # number of platforms # needed at a time plat_needed = 1 result = 1 i = 1 j = 0 # Similar to merge in # merge sort to process # all events in sorted order while (i < n and j < n): # If next event in sorted # order is arrival, # increment count of # platforms needed if (arr[i] <= dep[j]): plat_needed += 1 i += 1 # Else decrement count # of platforms needed elif (arr[i] > dep[j]): plat_needed -= 1 j += 1 # Update result if needed if (plat_needed > result): result = plat_needed return result# Driver codearr = [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))# This code is contributed# by Anant Agarwal. |
Javascript
<script>// Javascript Program to find minimum number // of platforms required on a railway// station// Returns minimum number of// platforms requiredfunction findPlatform(arr, dep, n){ // Sort arrival and // departure arrays arr = arr.sort((a,b) => a-b)); dep = dep.sort((a,b) => a-b)); // plat_needed indicates // number of platforms // needed at a time let plat_needed = 1; let result = 1; let i = 1; let j = 0; // Similar to merge in // merge sort to process // all events in sorted order while (i < n && j < n) { // If next event in sorted // order is arrival, increment // count of platforms needed if (arr[i] <= dep[j]) { plat_needed++; i++; } // Else decrement count // of platforms needed else if (arr[i] > dep[j]) { plat_needed--; j++; } // Update result if needed if (plat_needed > result) result = plat_needed; } return result;} // Driver Code let arr = new Array(900, 940, 950, 1100, 1500, 1800); let dep = new Array(910, 1200, 1120, 1130, 1900, 2000); let n = arr.length; document.write("Minimum Number of Platforms Required = " + findPlatform(arr, dep, n));// This code is contributed by Saurabh Jaiswal.</script> |
C#
// C# program to find minimum number// of platformsusing System;class GFG { // Returns minimum number of platforms // required static int findPlatform(int[] arr, int[] dep, int n) { // Sort arrival and departure arrays Array.Sort(arr); Array.Sort(dep); // plat_needed indicates number of // platforms needed at a time int plat_needed = 1, result = 1; int i = 1, j = 0; // Similar to merge in merge sort // to process all events in sorted // order while (i < n && j < n) { // If next event in sorted order // is arrival, increment count // of platforms needed if (arr[i] <= dep[j]) { plat_needed++; i++; } // Else decrement count of // platforms needed else if (arr[i] > dep[j]) { plat_needed--; j++; } // Update result if needed if (plat_needed > result) result = plat_needed; } return result; } // Driver code public static void Main() { int[] arr = { 900, 940, 950, 1100, 1500, 1800 }; int[] dep = { 910, 1200, 1120, 1130, 1900, 2000 }; int n = arr.Length; Console.Write("Minimum Number of " + " Platforms Required = " + findPlatform(arr, dep, n)); }}// This code os contributed by nitin mittal. |
PHP
<?php// PHP Program to find minimum number // of platforms required on a railway// station// Returns minimum number of// platforms requiredfunction findPlatform($arr, $dep, $n){ // Sort arrival and // departure arrays sort($arr); sort($dep); // plat_needed indicates // number of platforms // needed at a time $plat_needed = 1; $result = 1; $i = 1; $j = 0; // Similar to merge in // merge sort to process // all events in sorted order while ($i < $n and $j < $n) { // If next event in sorted // order is arrival, increment // count of platforms needed if ($arr[$i] <= $dep[$j]) { $plat_needed++; $i++; } // Else decrement count // of platforms needed elseif ($arr[$i] > $dep[$j]) { $plat_needed--; $j++; } // Update result if needed if ($plat_needed > $result) $result = $plat_needed; } return $result;} // Driver Code $arr = array(900, 940, 950, 1100, 1500, 1800); $dep = array(910, 1200, 1120, 1130, 1900, 2000); $n = count($arr); echo "Minimum Number of Platforms Required = ", findPlatform($arr, $dep, $n);// This code is contributed by anuj_67.?> |
Output
3
Time Complexity: O(N * log N), One traversal O(n) of both the array is needed after sorting O(N * log N).
Auxiliary space: O(1), As no extra space is required.
Minimum Number of Platforms Required for a Railway/Bus Station using Sweep Line Algorithm:
The sweep line algorithm is an efficient method for solving problems involving intervals or segments, and can be used to solve the problem of finding the minimum number of platforms needed at a train station based on the arrival and departure times of trains. The algorithm maintains a count of the number of platforms needed at each time, which is used to determine the minimum number of platforms needed at the station.
By using the idea behind this article: Constant time range add operation on an array
When a train arrives at the station, we increase the count by 1 because it occupies a platform. Similarly, when a train departs from the station, we decrease the count by 1 because it frees up a platform.
We first create a vector of size maxDepartureTime+2 and initialize all its values to 0. We then iterate over the input arrays and increment the count at the arrival time and decrement the count at the departure time in the vector. At any point in time, the sum of values (cumulative sum) in the vector will give us the number of trains present at the station. We can then find the maximum of this sum, which will give us the minimum number of platforms required.
Illustration:
Follow the steps mentioned below:
- Initialize a variable count to 0.
- Create a vector v of size maxDepartureTime+2 and initialize all its values to 0.
- Iterate over the input arrays and increment the value at the arrival time in v and decrement the value at the departure time+1 in v.
- Iterate over the vector v and keep track of the maximum sum seen so far. This maximum sum will give us the minimum number of platforms required.
- Return the maximum sum.
Below is the implementation of the above approach:
C++
// C++ program to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number of platforms// requiredint findPlatformOptimized(int arr[], int dep[], int n){ int count = 0, maxPlatforms = 0; // Find the maximum departure time int maxDepartureTime = dep[0]; for (int i = 1; i < n; i++) { maxDepartureTime = max(maxDepartureTime, dep[i]); } // Create a vector to store the count of trains at each // time vector<int> v(maxDepartureTime + 2, 0); // Increment the count at the arrival time and decrement // at the departure time for (int i = 0; i < n; i++) { v[arr[i]]++; v[dep[i] + 1]--; } // Iterate over the vector and keep track of the maximum // sum seen so far for (int i = 0; i <= maxDepartureTime + 1; i++) { count += v[i]; maxPlatforms = max(maxPlatforms, count); } return maxPlatforms;}// Driver Codeint main(){ int arr[] = { 100, 300, 600 }; int dep[] = { 900, 400, 500 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findPlatformOptimized(arr, dep, n); return 0;} |
Java
import java.util.*;public class Main { // Function to find the minimum number of platforms required public static int findPlatformOptimized(int[] arr, int[] dep, int n) { int count = 0, maxPlatforms = 0; // Find the maximum departure time int maxDepartureTime = dep[0]; for (int i = 1; i < n; i++) { maxDepartureTime = Math.max(maxDepartureTime, dep[i]); } // Create a vector to store the count of trains at each time List<Integer> v = new ArrayList<>(maxDepartureTime + 2); for (int i = 0; i < maxDepartureTime + 2; i++) { v.add(0); } // Increment the count at the arrival time and decrement at the departure time for (int i = 0; i < n; i++) { v.set(arr[i], v.get(arr[i]) + 1); v.set(dep[i] + 1, v.get(dep[i] + 1) - 1); } // Iterate over the vector and keep track of the maximum sum seen so far for (int i = 0; i <= maxDepartureTime + 1; i++) { count += v.get(i); maxPlatforms = Math.max(maxPlatforms, count); } return maxPlatforms; } // Driver Code public static void main(String[] args) { int[] arr = { 100, 300, 600 }; int[] dep = { 900, 400, 500 }; int n = arr.length; System.out.println(findPlatformOptimized(arr, dep, n)); }} |
Python3
from typing import List# Function to find the minimum number of platforms required.def find_platform_optimized(arr: List[int], dep: List[int], n: int) -> int: count = 0 max_platforms = 0 # Find the maximum departure time max_departure_time = max(dep) # Create a list to store the count of trains at each time v = [0] * (max_departure_time + 2) # Increment the count at the arrival time and decrement at the departure time for i in range(n): v[arr[i]] += 1 v[dep[i] + 1] -= 1 # Iterate over the list and keep track of the maximum sum seen so far for i in range(max_departure_time + 2): count += v[i] max_platforms = max(max_platforms, count) return max_platforms# Driver Codeif __name__ == '__main__': arr = [100, 300, 600] dep = [900, 400, 500] n = len(arr) print(find_platform_optimized(arr, dep, n)) |
Javascript
// Function to find the minimum number of platforms// requiredfunction findPlatformOptimized(arr, dep, n) { let count = 0, maxPlatforms = 0; // Find the maximum departure time let maxDepartureTime = dep[0]; for (let i = 1; i < n; i++) { maxDepartureTime = Math.max(maxDepartureTime, dep[i]); } // Create an array to store the count of trains at each // time const v = new Array(maxDepartureTime + 2).fill(0); // Increment the count at the arrival time and decrement // at the departure time for (let i = 0; i < n; i++) { v[arr[i]]++; v[dep[i] + 1]--; } // Iterate over the array and keep track of the maximum // sum seen so far for (let i = 0; i <= maxDepartureTime + 1; i++) { count += v[i]; maxPlatforms = Math.max(maxPlatforms, count); } return maxPlatforms;}// Driver Codeconst arr = [100, 300, 600];const dep = [900, 400, 500];const n = arr.length;console.log(findPlatformOptimized(arr, dep, n)); |
C#
using System;using System.Collections.Generic;class Program { static int FindPlatformOptimized(int[] arr, int[] dep, int n) { int count = 0, maxPlatforms = 0; // Find the maximum departure time int maxDepartureTime = dep[0]; for (int i = 1; i < n; i++) { maxDepartureTime = Math.Max(maxDepartureTime, dep[i]); } // Create a list to store the count of trains at // each time List<int> v = new List<int>(maxDepartureTime + 2); for (int i = 0; i <= maxDepartureTime + 1; i++) { v.Add(0); } // Increment the count at the arrival time and // decrement at the departure time for (int i = 0; i < n; i++) { v[arr[i]]++; v[dep[i] + 1]--; } // Iterate over the list and keep track of the // maximum sum seen so far for (int i = 0; i <= maxDepartureTime + 1; i++) { count += v[i]; maxPlatforms = Math.Max(maxPlatforms, count); } return maxPlatforms; } static void Main(string[] args) { int[] arr = { 100, 300, 600 }; int[] dep = { 900, 400, 500 }; int n = arr.Length; Console.WriteLine( FindPlatformOptimized(arr, dep, n)); }}// This code is contributed by sarojmcy2e |
Output
2
Complexity Analysis:
- Time Complexity: O(n), where n is the number of trains. The algorithm iterates over the input arrays once to update the vector, and then iterates over the vector once to calculate the cumulative sum. Both iterations take O(n) time. The space complexity of the algorithm is O(1) as the vector used has a fixed size.
- Auxiliary space: O(maxDepartureTime), as we create a vector of size maxDepartureTime+2 to store the count of trains at each time.
Note: There is one more approach to the problem, which uses O(n) extra space and O(n) time to solve the problem:
Minimum Number of Platforms Required for a Railway/Bus Station | Set 2 (Map-based approach)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
