Table of contents

Minimum number of Platforms

Given arrival and departure times of trains at a railway station, find the minimum number of platforms required so that no train has to wait. Each train needs one platform, and trains arriving and departing at the same time do not require an additional platform.

Input/Output Examples

plaintext
Example 1:
Input:
arrivals = [900, 940, 950, 1100, 1500, 1800]
departures = [910, 1200, 1120, 1130, 1900, 2000]
Output: 3
Explanation: At 11:00 AM, three trains are at the station, so three platforms are needed.

Example 2:
Input:
arrivals = [900, 1100, 1235]
departures = [1000, 1200, 1240]
Output: 1
Explanation: At most, only one train is at the station at any given time, so only one platform is needed.

Approach to find the minimum number of platforms required

  1. Sort the Arrival and Departure Times:
    • Begin by sorting both the arrivals and departures arrays. This allows us to handle the trains in chronological order, making it easier to keep track of how many platforms are needed at any time.
  2. Use Two Pointers to Track Platforms Needed:
    • Initialize two pointers: i for the arrivals array and j for the departures array. These pointers will help in determining when a train arrives and departs.
    • Keep track of the current number of platforms needed using platforms_needed, and update max_platforms to store the maximum platforms required at any time.
  3. Increment or Decrement Platforms:
    • Traverse through the arrays using the pointers:
      • If arrivals[i] is less than or equal to departures[j], a train arrives, so increment platforms_needed and move i to the next arrival.
      • If arrivals[i] is greater than departures[j], a train departs, so decrement platforms_needed and move j to the next departure.
    • Update max_platforms to be the maximum value of platforms_needed throughout the traversal.

C++ Program to find the minimum number of platforms required

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to find the minimum number of platforms required
int findMinPlatforms(vector<int>& arrivals, vector<int>& departures) {
    // Sort arrival and departure times
    sort(arrivals.begin(), arrivals.end());
    sort(departures.begin(), departures.end());

    int platforms_needed = 0, max_platforms = 0;
    int i = 0, j = 0;

    // Traverse through all trains using arrival and departure times
    while (i < arrivals.size() && j < departures.size()) {
        if (arrivals[i] <= departures[j]) {
            // A train has arrived, increase platform count
            platforms_needed++;
            i++;
        } else {
            // A train has departed, decrease platform count
            platforms_needed--;
            j++;
        }
        // Update the maximum platforms needed
        max_platforms = max(max_platforms, platforms_needed);
    }

    return max_platforms;
}

int main() {
    vector<int> arrivals = {900, 940, 950, 1100, 1500, 1800};
    vector<int> departures = {910, 1200, 1120, 1130, 1900, 2000};
    cout << "Minimum platforms required: " << findMinPlatforms(arrivals, departures) << endl;
    return 0;
}

Java Program to find the minimum number of platforms required

java
import java.util.Arrays;

public class MinimumPlatforms {

    // Function to find the minimum number of platforms required
    public static int findMinPlatforms(int[] arrivals, int[] departures) {
        // Sort arrival and departure times
        Arrays.sort(arrivals);
        Arrays.sort(departures);

        int platforms_needed = 0, max_platforms = 0;
        int i = 0, j = 0;

        // Traverse through all trains using arrival and departure times
        while (i < arrivals.length && j < departures.length) {
            if (arrivals[i] <= departures[j]) {
                // A train has arrived, increase platform count
                platforms_needed++;
                i++;
            } else {
                // A train has departed, decrease platform count
                platforms_needed--;
                j++;
            }
            // Update the maximum platforms needed
            max_platforms = Math.max(max_platforms, platforms_needed);
        }

        return max_platforms;
    }

    public static void main(String[] args) {
        int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
        int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
        System.out.println("Minimum platforms required: " + findMinPlatforms(arrivals, departures));
    }
}

Python Program to find the minimum number of platforms required

python
# Function to find the minimum number of platforms required
def find_min_platforms(arrivals, departures):
    # Sort arrival and departure times
    arrivals.sort()
    departures.sort()

    platforms_needed = 0
    max_platforms = 0
    i = 0
    j = 0

    # Traverse through all trains using arrival and departure times
    while i < len(arrivals) and j < len(departures):
        if arrivals[i] <= departures[j]:
            # A train has arrived, increase platform count
            platforms_needed += 1
            i += 1
        else:
            # A train has departed, decrease platform count
            platforms_needed -= 1
            j += 1
        # Update the maximum platforms needed
        max_platforms = max(max_platforms, platforms_needed)

    return max_platforms

# Example usage
if __name__ == "__main__":
    arrivals = [900, 940, 950, 1100, 1500, 1800]
    departures = [910, 1200, 1120, 1130, 1900, 2000]
    print("Minimum platforms required:", find_min_platforms(arrivals, departures))

Time Complexity: O(n log n) due to sorting. 
Space Complexity: O(1) due to the use of constant extra space for counting.

DSA

Related Articles