You are given two arrays representing the arrival and departure times of all trains that pass through a railway station. The times are provided in a 24-hour military integer format where 900 means 9:00 AM and 1830 means 6:30 PM. Find the absolute minimum number of platforms required at the railway station so that no train is ever kept waiting outside.
Standard railway rules dictate that if a train arrives at the exact same minute that another train departs, the departing train has not fully cleared the track yet. You must assign a new platform to the arriving train to prevent a collision.
Example 1
Input: arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000]
Output: 3
Explanation: At 9:40, the second train arrives while the first train has already departed, meaning 1 platform is needed. At 9:50, the third train arrives while the second train is still there, bringing the total to 2. At 11:00, the fourth train arrives while both the second and third trains are still stationed, peaking at 3 platforms needed at the exact same time.
Example 2
Input: arr = [900, 1100, 1235], dep = [1000, 1200, 1240]
Output: 1
Explanation: Every single train arrives strictly after the previous train has fully departed. A single platform can service all of them sequentially.
Brute Force Approach
The most direct way to think about the problem is to stand at every train arrival time and ask: How many trains are already at the station right now? This works because the number of occupied platforms can increase only when a train arrives. Departures reduce the need for platforms, but arrivals are the moments where a new platform may suddenly become necessary.
So, for each arrival time, check all trains and count how many of them have already arrived but not departed yet. The largest such count is the answer.
Algorithm
Start with
minimumPlatformsas0. This will store the highest number of trains found at the station at the same time.Pick each arrival time one by one. This is done because platform demand can increase only when a new train arrives.
For the chosen arrival time, scan all trains and count how many trains are present at that exact time.
A train is present if its arrival time is less than or equal to the chosen time, and its departure time is greater than or equal to the chosen time.
Update
minimumPlatformswith the largest count found so far because the station must be ready for the busiest moment.
Dry Run
railway
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Finds the minimum platforms by checking every arrival time as a possible busy moment. */ int minimumPlatforms(vector<int>& arr, vector<int>& dep) { int n = arr.size(); // This stores the maximum number of trains // present together at any checked arrival time. int minimumPlatforms = 0; for (int i = 0; i < n; i++) { // This stores how many trains are present // at the current train's arrival time. int trainsPresent = 0; for (int j = 0; j < n; j++) { // A train is present if it has already arrived // and has not departed before this moment. if (arr[j] <= arr[i] && dep[j] >= arr[i]) { trainsPresent++; } } // The answer must cover the busiest moment seen so far. minimumPlatforms = max(minimumPlatforms, trainsPresent); } return minimumPlatforms; }};// Driver code startsint main() { vector<int> arr = {900, 940, 950, 1100, 1500, 1800}; vector<int> dep = {910, 1200, 1120, 1130, 1900, 2000}; Solution sol; cout << sol.minimumPlatforms(arr, dep) << endl; return 0;}Complexity Analysis
Time Complexity: O(N2), because for every arrival time, all trains are scanned.
Space Complexity: O(1), because constant space is used.
Optimal Approach
Instead of checking every train against every other train, look at the station timeline.
Only two types of events matter:
a train arrives, so one more platform may be needed
a train departs, so one platform becomes free
If all arrival times are sorted and all departure times are sorted, the next event can be found by comparing the earliest unprocessed arrival with the earliest unprocessed departure.
If the next arrival happens before or at the same time as the next departure, a new train has entered while the previous train has not freed its platform yet. So the current platform count increases.
If the next departure happens before the next arrival, one train has left before another train enters. So one platform becomes free.
The maximum value reached by the current platform count is the minimum number of platforms required.
Algorithm
Sort the arrival array so trains are processed in the order they reach the station. This makes it easy to know the next train that may need a platform.
Sort the departure array so the earliest platform-freeing time is always visible. This helps decide whether an existing platform can be reused.
Keep two pointers: one for arrivals and one for departures. These pointers compare the next arrival with the earliest pending departure.
If the next arrival time is less than or equal to the next departure time, increase the current platform count because this train cannot reuse that still-occupied platform.
Otherwise, decrease the current platform count because a train has departed before the next arrival, freeing one platform.
Track the largest current platform count during the sweep. That largest value is the answer because it represents the busiest moment at the station.
Dry Run
Minimum Number of Platforms Required Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Finds the minimum platforms using sorted arrivals, sorted departures, and two pointers. */ int minimumPlatforms(vector<int>& arr, vector<int>& dep) { sort(arr.begin(), arr.end()); sort(dep.begin(), dep.end()); int n = arr.size(); // This pointer tracks the next arrival to process. int arrivalIndex = 0; // This pointer tracks the earliest pending departure. int departureIndex = 0; // This stores how many platforms are occupied right now. int currentPlatforms = 0; // This stores the maximum platforms needed at any time. int answer = 0; while (arrivalIndex < n) { // If the next train arrives before the earliest // pending train leaves, a new platform is needed. if (arr[arrivalIndex] <= dep[departureIndex]) { currentPlatforms++; // The maximum occupied count is the required answer. answer = max(answer, currentPlatforms); arrivalIndex++; } else { // A train leaves before the next arrival, // so one occupied platform becomes free. currentPlatforms--; departureIndex++; } } return answer; }};// Driver code startsint main() { vector<int> arr = {900, 940, 950, 1100, 1500, 1800}; vector<int> dep = {910, 1200, 1120, 1130, 1900, 2000}; Solution sol; cout << sol.minimumPlatforms(arr, dep) << endl; return 0;}Complexity Analysis
Time Complexity: O(N log N), because both arrays are sorted, and the two-pointer scan takes linear time.
Space Complexity: O(1) extra space, if sorting is done in place.
Interview follow-up Questions
Sorting them independently breaks the relationship between a specific train's arrival and its own departure. However, for calculating capacity, the identity of the train mathematically does not matter. An empty platform created by Train A can immediately be used by Train B. We only care about tracking the raw sequence of total arriving and departing events chronologically.
Be the first to add a comment.