AlgoViz
HomeGreedy

Minimum number of platforms required for a railway

Medium

Sort arrivals and departures separately

Problem

Given arrival and departure times of trains, find the minimum number of platforms needed so no train waits.

In simple words

Sort arrivals and departures; sweep time counting trains present, tracking the busiest instant.

The idea

Sorting the two time lists independently and sweeping them together tracks how many trains are present at any instant. The peak of that running count is the number of platforms, and which train is which never matters.

The trick

  • Advance the arrival pointer and increment when arrival <= departure, else advance departures and decrement.
  • Track the running maximum, not the final value.
  • O(n log n) for the sorts.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

900
940
950
1100
1500
1800
0
1
2
3
4
5

Step 1 of 2. Here's the example — arr=[900,940,950,1100,1500,1800], dep=[910,1200,1120,1130,1900,2000] Values: 900, 940, 950, 1100, 1500, 1800.

1/2
Optimal
timeO(n log n)spaceO(1)
1sort(arr); sort(dep)2i=j=0; plat=0; best=03while i<n:4  if arr[i]<=dep[j]: plat++; i++; best=max(best,plat)5  else: plat--; j++6return best

Input

array
[900, 940, 950, 1100, 1500, 1800]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
arr = [900,940,950,1100,1500,1800], dep = [910,1200,1120,1130,1900,2000]
Output:
3
Explanation:
At the busiest moment, 3 trains overlap.

Example 2

Input:
arr = [900,1100,1235], dep = [1000,1200,1240]
Output:
1
Explanation:
No overlaps → 1 platform.

Example 3

Input:
arr = [200,210], dep = [230,240]
Output:
2
Explanation:
Both trains overlap → 2.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.