Question 16 : Find minimum number of platforms required for railway station

You are given the arrival and departure time of trains reaching a particular station. 

You need to find a minimum number of platforms required to accommodate the trains at any point in time.

For example:

arrival[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00}
departure[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00}
No. of platforms required in above scenario = 4

Please note that the arrival time is in chronological order.

Solution :

If you notice we need to find a maximum number of trains that can be at the station with the help of arrival and departure times.

Solution 1:

You can iterate over all intervals and check how many other intervals are overlapping with it but that will require o(N^2) time complexity.

 Solution 2:

We will use logic very much similar to merge sort.

• Sort both arrival(arr) and departure(dep) arrays.
• Compare current element in arrival and departure array and pick smaller one among both.
• If element is pick up from arrival array then increment platform_needed.
• If element is pick up from departure array then decrement platform_needed.
• While performing above steps, we need track count of maximum value reached for platform_needed.
• In the end, we will return maximum value reached for platform_needed.

Time complexity : O(NLogN)

Below diagram will make you understand above code better:

Java program for Minimum number of platform required for a railway station:

import java.util.Arrays;
 
public class TrainPlatformMain {
    public static void main(String args[])
    {
        // arr[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00}
        // dep[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00}
 
        int arr[] = {100, 140, 150, 200, 215, 400};
        int dep[] = {110, 300, 210, 230,315, 600};
        System.out.println("Minimum platforms needed:"+findPlatformsRequiredForStation(arr,dep,6));
    }
 
    static int findPlatformsRequiredForStation(int arr[], int dep[], int n)
    {
        int platform_needed = 0, maxPlatforms = 0;
        Arrays.sort(arr);
        Arrays.sort(dep);
        int i = 0, j = 0;
 
        // Similar to merge in merge sort
        while (i < n && j < n)
        {
            if (arr[i] < dep[j])
            {
                platform_needed++;
                i++;
                if (platform_needed > maxPlatforms)
                    maxPlatforms = platform_needed;
            }
            else
            {
                platform_needed--;
                j++;
            }
        }
        return maxPlatforms;
    }
}

Python code 

def min_platforms(arr, dep):
    arr.sort()
    dep.sort()
    plat_needed = 1
    result = 1
    i, j = 1, 0
    while i < len(arr) and j < len(dep):
        if arr[i] <= dep[j]:
            plat_needed += 1
            i += 1
        else:
            plat_needed -= 1
            j += 1
        result = max(result, plat_needed)
    return result
arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1200, 1120, 1130, 1900, 2000]
print(min_platforms(arr, dep))  # 3

Brute Force — Check Overlaps
For each train, count how many other trains overlap with it.

The maximum overlap at any point = required platforms.
🟦 Java — Brute Force
public class MinPlatformsBruteForce {

    public static int findMinPlatforms(int[] arr, int[] dep) {
        int n = arr.length;
        int maxPlatforms = 1;

        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = i + 1; j < n; j++) {
                // Check overlap
                if (arr[j] <= dep[i] && arr[i] <= dep[j]) {
                    count++;
                }
            }
            maxPlatforms = Math.max(maxPlatforms, count);
        }
        return maxPlatforms;
    }

    public static void main(String[] args) {
        int[] arr = {900, 940, 950, 1100};
        int[] dep = {910, 1200, 1120, 1130};
        System.out.println(findMinPlatforms(arr, dep));
    }
}
Python — Brute Force
def min_platforms_brute(arr, dep):
    n = len(arr)
    max_platforms = 1

    for i in range(n):
        count = 1
        for j in range(i + 1, n):
            if arr[j] <= dep[i] and arr[i] <= dep[j]:
                count += 1
        max_platforms = max(max_platforms, count)

    return max_platforms


arr = [900, 940, 950, 1100]
dep = [910, 1200, 1120, 1130]
print(min_platforms_brute(arr, dep))
2️⃣ Using Min Heap — Track Departures
Idea
Sort trains by arrival time
Use a min-heap to track the earliest departure
If a train arrives before the earliest departure → need new platform
Otherwise reuse a platform

🟦 Java — Min Heap 
import java.util.Arrays;
import java.util.PriorityQueue;

public class MinPlatformsHeap {

    public static int findMinPlatforms(int[] arr, int[] dep) {
        int n = arr.length;

        int[][] trains = new int[n][2];
        for (int i = 0; i < n; i++) {
            trains[i][0] = arr[i];
            trains[i][1] = dep[i];
        }

        Arrays.sort(trains, (a, b) -> a[0] - b[0]);

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(trains[0][1]);

        for (int i = 1; i < n; i++) {
            if (trains[i][0] > minHeap.peek()) {
                minHeap.poll(); // reuse platform
            }
            minHeap.add(trains[i][1]);
        }

        return minHeap.size();
    }

    public static void main(String[] args) {
        int[] arr = {900, 940, 950, 1100};
        int[] dep = {910, 1200, 1120, 1130};
        System.out.println(findMinPlatforms(arr, dep));
    }
}
Python — Min Heap
import heapq

def min_platforms_heap(arr, dep):
    trains = sorted(zip(arr, dep))
    heap = []

    heapq.heappush(heap, trains[0][1])

    for i in range(1, len(trains)):
        if trains[i][0] > heap[0]:
            heapq.heappop(heap)
        heapq.heappush(heap, trains[i][1])

    return len(heap)


arr = [900, 940, 950, 1100]
dep = [910, 1200, 1120, 1130]
print(min_platforms_heap(arr, dep))



  
    
    
    
    
  

  

    
Approach
    
Time Complexity
    
Space Complexity
    
Best Use
  

  

    

      Sort arrivals & departures + sweep
    
    

      O(n log n)
    
    

      O(1)
    
    

      ⭐ Best optimal solution
    
  

  

    

      Brute force (check overlaps)
    
    

      O(n²)
    
    

      O(1)
    
    

      ❌ Slow for large n
    
  

  

    

      Using min heap (heap of departures)
    
    

      O(n log n)
    
    

      O(n)
    
    

      ✔ Works but more overhead