Skip to main content
Back to ChallengesMinimum Platforms RequiredHard 45 min

Minimum Platforms Required

Given the arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train is kept waiting.

Examples

Input: arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000]
Output: 3
There are at most three trains at a time.

Constraints

  • • 1 <= N <= 10^5
  • • 0 <= arr[i] <= dep[i] <= 2359

Complexity Analysis

Time
O(N log N)
due to sorting both arrays.
Space
O(1) auxiliary space (or O(N) if copy needed).

Test Cases

#1 Standard case
Input: arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000]
Expected: 3
#2 No overlapping trains
Input: arr = [900, 1100, 1235], dep = [1000, 1200, 1240]
Expected: 1
Output
Click "Run Code" to see output here...