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...