Problem

Given a list of intervals representing the arrival and departure times of trains to a train station, our goal is to find the minimum number of platforms required for the train station so that no train has to wait.

Examples

Example 1:

Input: arrivals = [1000, 1010, 1025], departures = [1030, 1040, 1055]
Output: 2
Explanation: At time 1010, the second train arrives before the first one departs, so there must be 2 platforms available.

Example 2:

Input: arrivals = [900, 940, 950], departures = [910, 1000, 1100]
Output: 3
Explanation: All trains are at the station from 950 to 1000, hence 3 platforms are needed.

Solution

Method 1 - Sorting

This is same as - Maximum Intervals Overlap Count, with slight change in how we get the interval inputs.

The idea is to track the number of platforms occupied at any given time. By sorting both arrivals and departures first, we can iterate over them using two pointers (one for arrivals and one for departures). Each time a train arrives, we increment the count of platforms used. Each time a train departs, we decrement the count. The goal is to keep track of the maximum number of platforms used at any time during these operations to know the required number of platforms.

Here is the approach:

  1. Sort both the arrivals and departures arrays.
  2. Use two pointers: one for arrivals and one for departures.
  3. As you increment through the sorted arrivals and departures:
    • Increment platform count when a train arrives.
    • Decrement platform count when a train departs.
  4. Keep track of the maximum number of platforms needed during the iteration.

Code

Java
class Solution {
    public int findMinPlatforms(int[] arrivals, int[] departures) {
        int n = arrivals.length;
        Arrays.sort(arrivals);
        Arrays.sort(departures);
        
        int platforms = 0, maxPlatforms = 0;
        int i = 0, j = 0;
        
        while (i < n && j < n) {
            if (arrivals[i] <= departures[j]) {
                platforms++;
                maxPlatforms = Math.max(maxPlatforms, platforms);
                i++;
            } else {
                platforms--;
                j++;
            }
        }
        
        return maxPlatforms;
    }
}
Python
class Solution:
    def findMinPlatforms(self, arrivals: List[int], departures: List[int]) -> int:
        arrivals.sort()
        departures.sort()
        
        n = len(arrivals)
        platforms = 0
        max_platforms = 0
        i = 0
        j = 0
        
        while i < n and j < n:
            if arrivals[i] <= departures[j]:
                platforms += 1
                max_platforms = max(max_platforms, platforms)
                i += 1
            else:
                platforms -= 1
                j += 1
        
        return max_platforms

Complexity

  • ⏰ Time complexity: O(n log n) for sorting the arrival and departure arrays, where n is the number of trains.
  • 🧺 Space complexity: O(1) for the extra space used by the pointers and counters.