Minimum Number of Platforms in DSA Java

Mental Model

We want to find the smallest number of train platforms needed so that no train waits. We do this by checking how many trains overlap at the same time.

Analogy: Imagine a parking lot where cars arrive and leave at different times. We want to know the minimum number of parking spots so no car waits for a spot.

Time line:  
Arrivals:  |---|     |----|   |--|  
Departures:    |----|    |--|    |---|  
Platforms needed depends on how many intervals overlap.

Dry Run Walkthrough

Input: arrivals = [9:00, 9:40, 9:50, 11:00, 15:00, 18:00], departures = [9:10, 12:00, 11:20, 11:30, 19:00, 20:00]

Goal: Find the minimum number of platforms needed so that no train waits.

Step 1: Sort arrivals and departures separately

arrivals = [9:00, 9:40, 9:50, 11:00, 15:00, 18:00]
departures = [9:10, 11:20, 11:30, 12:00, 19:00, 20:00]

Why: Sorting helps us check events in chronological order.

Step 2: Compare first arrival (9:00) with first departure (9:10), arrival < departure, increment platform count to 1

platforms = 1, max_platforms = 1
Next arrival index = 1, departure index = 0

Why: A train arrives before the first one departs, so we need a platform.

Step 3: Compare arrival 9:40 with departure 9:10, arrival > departure, decrement platform count to 0

platforms = 0, max_platforms = 1
Next arrival index = 1, departure index = 1

Why: A train departs before next arrival, freeing a platform.

Step 4: Compare arrival 9:40 with departure 11:20, arrival < departure, increment platform count to 1

platforms = 1, max_platforms = 1
Next arrival index = 2, departure index = 1

Why: Train arrives before next departure, need platform.

Step 5: Compare arrival 9:50 with departure 11:20, arrival < departure, increment platform count to 2

platforms = 2, max_platforms = 2
Next arrival index = 3, departure index = 1

Why: Another train arrives before departure, need extra platform.

Step 6: Compare arrival 11:00 with departure 11:20, arrival < departure, increment platform count to 3

platforms = 3, max_platforms = 3
Next arrival index = 4, departure index = 1

Why: Another train arrives before departure, need another platform.

Step 7: Compare arrival 15:00 with departure 11:20, arrival > departure, decrement platform count to 2

platforms = 2, max_platforms = 3
Next arrival index = 4, departure index = 2

Why: Train departs, freeing platform.

Step 8: Compare arrival 15:00 with departure 11:30, arrival > departure, decrement platform count to 1

platforms = 1, max_platforms = 3
Next arrival index = 4, departure index = 3

Why: Train departs, freeing platform.

Step 9: Compare arrival 15:00 with departure 12:00, arrival > departure, decrement platform count to 0

platforms = 0, max_platforms = 3
Next arrival index = 4, departure index = 4

Why: Train departs, freeing platform.

Step 10: Compare arrival 15:00 with departure 19:00, arrival < departure, increment platform count to 1

platforms = 1, max_platforms = 3
Next arrival index = 5, departure index = 4

Why: Train arrives before departure, need platform.

Step 11: Compare arrival 18:00 with departure 19:00, arrival < departure, increment platform count to 2

platforms = 2, max_platforms = 3
Next arrival index = 6, departure index = 4

Why: Another train arrives before departure, need platform.

Step 12: No more arrivals, finish

max_platforms = 3

Why: Maximum platforms needed at any time was 3.

Result:

Final platforms needed: 3

Annotated Code

DSA Java

import java.util.Arrays;

public class MinimumPlatforms {

    public static int findMinPlatforms(int[] arrivals, int[] departures) {
        Arrays.sort(arrivals); // sort arrival times
        Arrays.sort(departures); // sort departure times

        int platformNeeded = 0, maxPlatforms = 0;
        int i = 0, j = 0;

        while (i < arrivals.length && j < departures.length) {
            if (arrivals[i] <= departures[j]) {
                platformNeeded++; // train arrives, need platform
                maxPlatforms = Math.max(maxPlatforms, platformNeeded); // update max
                i++; // move to next arrival
            } else {
                platformNeeded--; // train departs, free platform
                j++; // move to next departure
            }
        }

        return maxPlatforms;
    }

    public static void main(String[] args) {
        int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
        int[] departures = {910, 1200, 1120, 1130, 1900, 2000};

        int result = findMinPlatforms(arrivals, departures);
        System.out.println("Minimum number of platforms needed: " + result);
    }
}

Arrays.sort(arrivals); // sort arrival times

sort arrivals to process in chronological order

Arrays.sort(departures); // sort departure times

sort departures to process in chronological order

if (arrivals[i] <= departures[j]) {

check if next event is arrival before or at departure time

platformNeeded++; // train arrives, need platform

increment platform count for arriving train

maxPlatforms = Math.max(maxPlatforms, platformNeeded); // update max

track maximum platforms needed so far

i++; // move to next arrival

advance to next arrival event

platformNeeded--; // train departs, free platform

decrement platform count for departing train

j++; // move to next departure

advance to next departure event

Output

Minimum number of platforms needed: 3

Complexity Analysis

Time: O(n log n) because we sort the arrival and departure arrays each of size n

Space: O(1) because we use only a few extra variables, sorting done in place

vs Alternative: Naive approach checks every train against every other train leading to O(n^2) time, this approach is more efficient.

Edge Cases

No trains (empty arrays)

Returns 0 platforms needed

DSA Java

while (i < arrivals.length && j < departures.length) {

All trains arrive and depart at the same time

Platforms needed equals number of trains

DSA Java

platformNeeded++; // train arrives, need platform

Trains arrive after all previous trains depart

Platforms needed is 1

DSA Java

platformNeeded--; // train departs, free platform

When to Use This Pattern

When you see problems about scheduling overlapping intervals and need to find minimum resources, use the two-pointer approach on sorted start and end times to find maximum overlap.

Common Mistakes

Mistake: Not sorting arrival and departure arrays before processing
Fix: Sort both arrays to process events in chronological order

Mistake: Using < instead of <= in comparison, causing incorrect platform count when arrival equals departure
Fix: Use less than or equal (<=) to count arrivals at the same time as departures

Summary

Calculates the minimum number of platforms needed so no train waits.

Use when scheduling overlapping intervals to find maximum simultaneous events.

Sort arrivals and departures separately and use two pointers to track overlaps.

Practice

1. What does the "Minimum Number of Platforms" problem ask you to find given train arrival and departure times?

easy

A. The least number of platforms needed so no train waits

B. The total number of trains arriving in a day

C. The longest time a train stays on a platform

D. The earliest train arrival time

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of platforms required so that no train has to wait for another to leave.

2. Step 2: Clarify what is being counted

   We count how many trains overlap in time on the station to find the minimum platforms needed.

3. Final Answer:

   The least number of platforms needed so no train waits -> Option A

4. Quick Check:

   Minimum platforms = max trains overlapping [OK]

Hint: Count overlapping trains to find minimum platforms needed [OK]

Common Mistakes:

• Confusing total trains with platforms needed
• Ignoring overlapping times
• Counting earliest arrival only

2. Which Java data structure is best suited to efficiently find the minimum number of platforms needed given sorted arrival and departure arrays?

easy

A. PriorityQueue (Min-Heap)

B. Stack

C. LinkedList

D. HashMap

Solution

1. Step 1: Identify the need for quick minimum departure tracking

   We need to know the earliest train departure to free a platform, so a min-heap helps track minimum departure time efficiently.

2. Step 2: Match data structure to problem

   PriorityQueue in Java is a min-heap, perfect for this use case to manage platforms dynamically.

3. Final Answer:

   PriorityQueue (Min-Heap) -> Option A

4. Quick Check:

   Min-heap tracks earliest departure [OK]

Hint: Use min-heap to track earliest departure times [OK]

Common Mistakes:

• Using HashMap which doesn't maintain order
• Using Stack which is LIFO, not suitable
• Using LinkedList which is inefficient for min queries

3. What is the output of the following Java code snippet that calculates minimum platforms?

int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
System.out.println(minPlatforms(arrivals, departures));

// Assume minPlatforms returns the minimum platforms needed

medium

A. 2

B. 4

C. 3

D. 5

Solution

1. Step 1: Sort arrival and departure times

   Arrivals: 900, 940, 950, 1100, 1500, 1800 Departures: 910, 1120, 1130, 1200, 1900, 2000

2. Step 2: Count overlapping trains

   At 900-910: 1 train At 940-1120: 2 trains overlap At 950-1130: 3 trains overlap (max) After 1130, trains start leaving, so max platforms needed = 3

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Max overlap = 3 platforms [OK]

Hint: Find max overlapping intervals after sorting [OK]

Common Mistakes:

• Not sorting times before processing
• Counting total trains instead of overlaps
• Mixing arrival and departure arrays

4. Identify the bug in this Java method to find minimum platforms:

public static int minPlatforms(int[] arr, int[] dep) {
    Arrays.sort(arr);
    Arrays.sort(dep);
    int i = 0, j = 0, platforms = 0, maxPlatforms = 0;
    while (i < arr.length && j < dep.length) {
        if (arr[i] <= dep[j]) {
            platforms++;
            i++;
        } else {
            platforms--;
            j++;
        }
        maxPlatforms = Math.max(maxPlatforms, platforms);
    }
    return maxPlatforms;
}

medium

A. The loop should run while i < arr.length only

B. The condition should be arr[i] < dep[j] instead of <= to avoid counting simultaneous arrival and departure

C. The platforms variable should not be decremented

D. Arrays.sort should be called only on arrivals

Solution

1. Step 1: Analyze the comparison condition

   The condition arr[i] <= dep[j] counts a train arriving exactly when another departs as overlapping, increasing platforms unnecessarily.

2. Step 2: Correct the condition to avoid overcounting

   Changing to arr[i] < dep[j] treats simultaneous arrival and departure as no overlap, which is correct for platform counting.

3. Final Answer:

   The condition should be arr[i] < dep[j] instead of <= to avoid counting simultaneous arrival and departure -> Option B

4. Quick Check:

   Use strict less than for arrival vs departure [OK]

Hint: Use < not <= to avoid counting simultaneous arrival and departure [OK]

Common Mistakes:

• Using <= causes overcounting platforms
• Not sorting both arrays
• Incorrect loop condition

5. Given arrival times [1000, 1010, 1025, 1030, 1040] and departure times [1020, 1035, 1045, 1050, 1100], what is the minimum number of platforms needed if trains arriving exactly when another departs do NOT require a new platform?

hard

A. 4

B. 5

C. 2

D. 3

Solution

1. Step 1: Sort and analyze arrival and departure times

   Arrivals: 1000, 1010, 1025, 1030, 1040 Departures: 1020, 1035, 1045, 1050, 1100

2. Step 2: Count overlapping trains considering no extra platform if arrival equals departure

   1000-1020: 1 train 1010-1035: overlaps with first, total 2 1025-1045: first gone at 1020, overlaps with second, total 2 1030-1050: overlaps with second (till 1035) and third (till 1045), total 3 1040-1100: second gone at 1035, overlaps with third, fourth, total 3 (max)

3. Step 3: Adjust for arrival equals departure rule

   No arrivals equal departures here, so max platforms = 3

4. Final Answer:

   3 -> Option D

5. Quick Check:

   Max overlap = 3 platforms [OK]

Hint: Count overlaps, exclude equal arrival and departure as overlap [OK]

Common Mistakes:

• Counting equal arrival and departure as overlap
• Not sorting times
• Miscounting overlaps