Coding

Minimum number of platforms required for a railway

Asked at

J.P. Morgan

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given the arrival and departure times of all trains reaching a particular railway station, determine the minimum number of platforms required so that no train is kept waiting. Consider all trains arrive and depart on the same day.

In any particular instance, the same platform cannot be used for both the departure of one train and the arrival of another train, necessitating the use of different platforms in such cases.

Note: Time intervals are in the minutes , Leading zeros for minutes less than 1000 are optional (e.g., 0900 is the same as 900).

Input : Arrival = [900, 940, 950, 1100, 1500, 1800] , Departure = [910, 1200, 1120, 1130, 1900, 2000] Output : 3 Explanation : The first , second , fifth number train can use the platform 1.

The third and sixth train can use the platform 2.
The fourth train will use platform 3.
So total we need 3 different platforms for the railway station so that no train is kept waiting.

Input : Arrival = [900, 1100, 1235] , Departure = [1000, 1200, 1240] Output : 1 Explanation : All the three trains can use the platform 1.

So we required only 1 platform.

Input : Arrival = [900, 1000, 1200] , Departure = [1000, 1200, 1240]

1 <= N <= 105
0000 <= Arrival[i] <= Departure[i] <= 2359

cpp

class Solution{
    public:
    int findPlatform(vector<int>& Arrival, vector<int>& Departure){
        //your code goes here
    }
};

java

class Solution {
    public int findPlatform(int[] Arrival, int[] Departure) {
        //your code goes here
    }
}

python

class Solution:
    def findPlatform(self, Arrival, Departure):
        #your code goes here

javascript

class Solution {
    findPlatform(Arrival, Departure) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public int findPlatform(List<int> Arrival, List<int> Departure)
    {
        //your code goes here
    }
}

func findPlatform(Arrival []int, Departure []int) int {
	//your code goes here
}

Stuck? Show a way to structure it+

01Clarify whether arrival equal to departure needs a separate platform
02Sort arrivals and departures independently
03Advance the earlier event and update active count
04Record the maximum active count

Reference answer

Start by restating the input contract for Minimum number of platforms required for a railway and testing the smallest boundary case before choosing the algorithm. Sort arrival and departure times separately, then sweep with two pointers. An arrival before or at the next departure needs another platform; otherwise a train departs and frees one. Track the maximum number simultaneously present. Explain the invariant while coding, then show how each update preserves it. Sorting is O(n log n) time and the two-pointer sweep is O(n); auxiliary space is O(1) when the two input arrays are sorted in place. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

How do you return the busiest time window?
Tests: complexity analysis
How would you handle trains crossing midnight?
Tests: follow-up reasoning

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question