Problem Statement:
You are given an array of arrival and departure timings for train at a station.
You need to find the minimum umber of platforms required such that no train waits.
Example
arrival[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00} departure[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00} Output: 3 This is because, in the time interval from 11 to 12 there are 3 trains present at the station.
Solution
We can solve this problem in 2 different ways.
Method 1: Brute Force approach O(n^2)
We can get the arrival and departure for each train and compare it with the schedule.
The maximum of all these numbers will be the total platform needed.
Example:
Arrival Time Departure Time Train-1 9:00 9:10 Train-2 9:40 12:00 <- Train-3 9:50 11:20 <- Train-4 11:00 11:30 <- Train-5 15:30 19:15 Train-6 18:00 20:00
Method 2: Greedy Approach O(log(n)) time
If we observe the question, we need to find out how many trains will have an overlapping schedule.
It means, if there is a train, Train A, and we need to find if there are any trains arriving before the arrival of a train.
So we need to sort both of the arrays combined. Then we need to check if there are any trains whose departures are after the arrival of a train.
After sorting, we will keep track of the platforms needed.
Time Event Total Platforms Needed 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 0
Solution in C++
#include<iostream> #include<vector> #include<algorithm> #include<unordered_set> using namespace std; int get_min_num_platform_brute_force(int arrival[], int departure[], int n) { int platforms = 1; int result = 1; for(int i = 0; i<n; i++) { platforms = 1; for(int j = i+1; j<n; j++) { if ((arrival[i] >= arrival[j] && arrival[i] <= departure[j]) || (arrival[j] >= arrival[i] && arrival[j] <= departure[i])) { platforms++; } } result = max(result, platforms); } return result; } int get_min_num_platform_greedy(int arrival[], int departure[], int n) { int platforms = 1; int result = 1; sort(arrival, arrival + n); sort(departure, departure + n); int i=1; int j=0; while(i<n && j<n) { if(arrival[i]<=departure[j]) { platforms++; i++; }else if(departure[j]<arrival[i]){ // else decrease the number of platforms required platforms--; j++; } result = max(platforms,result); } return result; } 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 << "The min num of platform required using brute force approach are " << get_min_num_platform_brute_force(arrival, departure, n)<<endl; cout << "The min num of platform required using greedy approach are " << get_min_num_platform_greedy(arrival, departure, n)<<endl; return 0; }
Output:
The min num of platform required using brute force approach are 3 The min num of platform required using greedy approach are 3