Minimum Number of Platforms

Given arrival and departure times of trains at a station, find the minimum number of platforms required so that no train is kept waiting

Language Selection

Choose your preferred programming language

Showing: Python

Minimum Number of Platforms

Problem Statement

Given two arrays arrival[] and departure[] which represent the arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required at the station so that no train has to wait.

A platform is occupied from the arrival time of a train until its departure time. If a train departs at time t and another arrives at time t, they can share the same platform (the departing train leaves before the arriving train takes the platform).

Constraints:

  • 1 <= n <= 10^5 (number of trains)
  • 0 <= arrival[i] < departure[i] <= 2359
  • All times are given in 24-hour format (HHMM)

Examples:

Example 1:

Input: arrival = [900, 940, 950, 1100, 1500, 1800]
       departure = [910, 1200, 1120, 1130, 1900, 2000]
Output: 3
Explanation: Between 950 and 1100, trains arriving at 940, 950, and 1100 are all at the station.
The maximum overlap is 3, so 3 platforms are needed.

Example 2:

Input: arrival = [900, 1100, 1235]
       departure = [920, 1200, 1240]
Output: 1
Explanation: No two trains overlap, so only 1 platform is needed.

Example 3:

Input: arrival = [100, 300, 500]
       departure = [200, 400, 600]
Output: 1
Explanation: Each train departs before the next arrives.

Example 4:

Input: arrival = [100, 100, 100]
       departure = [200, 200, 200]
Output: 3
Explanation: All three trains arrive at the same time and overlap completely.

Approach 1: Naive (Check All Pairs)

Algorithm:

  1. For each train, count how many other trains are present at the station during its stay
  2. A train j overlaps with train i if arrival[j] <= departure[i] and departure[j] >= arrival[i]
  3. The maximum count across all trains is the answer

Time Complexity: O(n^2) Space Complexity: O(1)

Python:

def findPlatform(arrival, departure):
    """
    Find minimum platforms using brute force approach
    Time: O(n^2)
    Space: O(1)
    """
    n = len(arrival)
    if n == 0:
        return 0

    max_platforms = 1

    for i in range(n):
        count = 1
        for j in range(n):
            if i != j:
                # Train j overlaps with train i
                if arrival[j] <= departure[i] and departure[j] >= arrival[i]:
                    count += 1
        max_platforms = max(max_platforms, count)

    return max_platforms

Java:

class Solution {
    /**
     * Find minimum platforms using brute force approach
     * Time: O(n^2)
     * Space: O(1)
     */
    public int findPlatform(int[] arrival, int[] departure) {
        int n = arrival.length;
        if (n == 0) return 0;

        int maxPlatforms = 1;

        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    if (arrival[j] <= departure[i] && departure[j] >= arrival[i]) {
                        count++;
                    }
                }
            }
            maxPlatforms = Math.max(maxPlatforms, count);
        }

        return maxPlatforms;
    }
}

Go:

// findPlatform - Find minimum platforms using brute force
// Time: O(n^2)
// Space: O(1)
func findPlatform(arrival []int, departure []int) int {
    n := len(arrival)
    if n == 0 {
        return 0
    }

    maxPlatforms := 1

    for i := 0; i < n; i++ {
        count := 1
        for j := 0; j < n; j++ {
            if i != j {
                if arrival[j] <= departure[i] && departure[j] >= arrival[i] {
                    count++
                }
            }
        }
        if count > maxPlatforms {
            maxPlatforms = count
        }
    }

    return maxPlatforms
}

JavaScript:

/**
 * Find minimum platforms using brute force approach
 * Time: O(n^2)
 * Space: O(1)
 */
function findPlatform(arrival, departure) {
    const n = arrival.length;
    if (n === 0) return 0;

    let maxPlatforms = 1;

    for (let i = 0; i < n; i++) {
        let count = 1;
        for (let j = 0; j < n; j++) {
            if (i !== j) {
                if (arrival[j] <= departure[i] && departure[j] >= arrival[i]) {
                    count++;
                }
            }
        }
        maxPlatforms = Math.max(maxPlatforms, count);
    }

    return maxPlatforms;
}

C#:

public class Solution {
    /// <summary>
    /// Find minimum platforms using brute force approach
    /// Time: O(n^2)
    /// Space: O(1)
    /// </summary>
    public int FindPlatform(int[] arrival, int[] departure) {
        int n = arrival.Length;
        if (n == 0) return 0;

        int maxPlatforms = 1;

        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    if (arrival[j] <= departure[i] && departure[j] >= arrival[i]) {
                        count++;
                    }
                }
            }
            maxPlatforms = Math.Max(maxPlatforms, count);
        }

        return maxPlatforms;
    }
}

Approach 2: Sorting-Based Sweep Line (Optimal)

Algorithm:

  1. Sort arrival times and departure times independently
  2. Use two pointers to traverse both sorted arrays simultaneously
  3. If the next event is an arrival, increment the platform count
  4. If the next event is a departure, decrement the platform count
  5. When arrival equals departure, process departure first (a departing train frees the platform for an arriving one)
  6. Track the maximum platform count seen at any point

Time Complexity: O(n log n) for sorting Space Complexity: O(1) if sorting in-place (or O(n) for sorted copies)

Python:

def findPlatform(arrival, departure):
    """
    Find minimum platforms using sorting-based sweep line
    Time: O(n log n)
    Space: O(1) if in-place sort
    """
    n = len(arrival)
    if n == 0:
        return 0

    arrival.sort()
    departure.sort()

    platforms_needed = 0
    max_platforms = 0
    i = 0  # pointer for arrivals
    j = 0  # pointer for departures

    while i < n:
        if arrival[i] <= departure[j]:
            # A train arrives: need one more platform
            platforms_needed += 1
            max_platforms = max(max_platforms, platforms_needed)
            i += 1
        else:
            # A train departs: free one platform
            platforms_needed -= 1
            j += 1

    return max_platforms

Java:

import java.util.Arrays;

class Solution {
    /**
     * Find minimum platforms using sorting-based sweep line
     * Time: O(n log n)
     * Space: O(1) if in-place sort
     */
    public int findPlatform(int[] arrival, int[] departure) {
        int n = arrival.length;
        if (n == 0) return 0;

        Arrays.sort(arrival);
        Arrays.sort(departure);

        int platformsNeeded = 0;
        int maxPlatforms = 0;
        int i = 0; // pointer for arrivals
        int j = 0; // pointer for departures

        while (i < n) {
            if (arrival[i] <= departure[j]) {
                platformsNeeded++;
                maxPlatforms = Math.max(maxPlatforms, platformsNeeded);
                i++;
            } else {
                platformsNeeded--;
                j++;
            }
        }

        return maxPlatforms;
    }
}

Go:

import "sort"

// findPlatform - Find minimum platforms using sorting-based sweep line
// Time: O(n log n)
// Space: O(1) if in-place sort
func findPlatform(arrival []int, departure []int) int {
    n := len(arrival)
    if n == 0 {
        return 0
    }

    sort.Ints(arrival)
    sort.Ints(departure)

    platformsNeeded := 0
    maxPlatforms := 0
    i := 0 // pointer for arrivals
    j := 0 // pointer for departures

    for i < n {
        if arrival[i] <= departure[j] {
            platformsNeeded++
            if platformsNeeded > maxPlatforms {
                maxPlatforms = platformsNeeded
            }
            i++
        } else {
            platformsNeeded--
            j++
        }
    }

    return maxPlatforms
}

JavaScript:

/**
 * Find minimum platforms using sorting-based sweep line
 * Time: O(n log n)
 * Space: O(1) if in-place sort
 */
function findPlatform(arrival, departure) {
    const n = arrival.length;
    if (n === 0) return 0;

    arrival.sort((a, b) => a - b);
    departure.sort((a, b) => a - b);

    let platformsNeeded = 0;
    let maxPlatforms = 0;
    let i = 0; // pointer for arrivals
    let j = 0; // pointer for departures

    while (i < n) {
        if (arrival[i] <= departure[j]) {
            platformsNeeded++;
            maxPlatforms = Math.max(maxPlatforms, platformsNeeded);
            i++;
        } else {
            platformsNeeded--;
            j++;
        }
    }

    return maxPlatforms;
}

C#:

using System;

public class Solution {
    /// <summary>
    /// Find minimum platforms using sorting-based sweep line
    /// Time: O(n log n)
    /// Space: O(1) if in-place sort
    /// </summary>
    public int FindPlatform(int[] arrival, int[] departure) {
        int n = arrival.Length;
        if (n == 0) return 0;

        Array.Sort(arrival);
        Array.Sort(departure);

        int platformsNeeded = 0;
        int maxPlatforms = 0;
        int i = 0; // pointer for arrivals
        int j = 0; // pointer for departures

        while (i < n) {
            if (arrival[i] <= departure[j]) {
                platformsNeeded++;
                maxPlatforms = Math.Max(maxPlatforms, platformsNeeded);
                i++;
            } else {
                platformsNeeded--;
                j++;
            }
        }

        return maxPlatforms;
    }
}

Key Insights

  1. Sorting Decouples Pairs: We sort arrivals and departures independently. This works because we only need to know when any train arrives and when any train departs, not which specific train is involved.

  2. Sweep Line Technique: By processing events (arrivals and departures) in chronological order, we maintain a running count of trains present at the station.

  3. Tie-Breaking Rule: When an arrival and departure happen at the same time, processing the departure first (via <=) is correct because the departing train frees the platform before the arriving train needs one.

  4. Two Pointers Sufficiency: Since both arrays are sorted, two pointers are enough to merge the event streams chronologically without actually merging the arrays.

  5. Independence of Train Identity: The minimum platforms depend only on the maximum overlap, not on which specific train is on which platform.

Edge Cases

  • Single train: arrival = [900], departure = [1000] → 1
  • No overlap: arrival = [100, 300, 500], departure = [200, 400, 600] → 1
  • Complete overlap: arrival = [100, 100, 100], departure = [200, 200, 200] → 3
  • Adjacent trains (depart = arrive): arrival = [100, 200], departure = [200, 300] → 1
  • All same time: arrival = [900, 900], departure = [900, 900] → 2
  • Large input: n = 10^5 trains → sorting approach handles efficiently

Test Cases

# Test case 1: Standard overlapping trains
assert findPlatform([900, 940, 950, 1100, 1500, 1800],
                    [910, 1200, 1120, 1130, 1900, 2000]) == 3

# Test case 2: No overlaps
assert findPlatform([900, 1100, 1235],
                    [920, 1200, 1240]) == 1

# Test case 3: All trains at same time
assert findPlatform([100, 100, 100],
                    [200, 200, 200]) == 3

# Test case 4: Single train
assert findPlatform([900],
                    [1000]) == 1

# Test case 5: Sequential trains sharing platform
assert findPlatform([100, 200, 300],
                    [200, 300, 400]) == 1

# Test case 6: Two trains fully overlapping
assert findPlatform([100, 150],
                    [300, 250]) == 2

# Test case 7: Tight schedule
assert findPlatform([900, 940, 950, 1100],
                    [910, 1200, 1120, 1130]) == 3

Common Mistakes

  1. Not sorting independently: Sorting arrival-departure pairs together (keeping them paired) is unnecessary and can lead to a more complex solution. Sorting them independently is both simpler and correct.

  2. Wrong tie-breaking: If arrivals are processed before departures at the same time, you may overcount platforms. When arrival equals departure, process departure first.

  3. Forgetting to track the maximum: Only counting at the end gives the final count, not the peak count. The maximum concurrent trains is the answer, not the count after all events.

  4. Off-by-one with departure pointer: The departure pointer j may not reach n since we stop when i reaches n. This is correct because all remaining departures happen after the last arrival.

  5. Modifying input arrays: If the original arrays must be preserved, create copies before sorting. The sorting-based approach modifies the input arrays in place.