Minimum Number of Platforms in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the 'Minimum Number of Platforms' problem about?

It is about finding the least number of train platforms needed at a station so that no train has to wait for another to leave.

beginner

What technique is commonly used to solve the Minimum Number of Platforms problem efficiently?

Sorting arrays of arrival and departure times separately and then using two pointers to traverse them.

intermediate

Why do we sort arrival and departure times separately in this problem?

Sorting helps us process events in chronological order to know when trains arrive and leave, so we can track platform usage accurately.

intermediate

What does it mean when arrival time is less than or equal to departure time during traversal?

It means a train arrives before the previous one leaves, so we need an extra platform.

intermediate

How do you update the count of platforms needed during the traversal?

Increase count when a train arrives before the previous departs; decrease count when a train departs before the next arrives. Keep track of the maximum count reached.

What is the first step to solve the Minimum Number of Platforms problem?

A Assign platforms randomly

B Count total trains

C Sort arrival and departure times separately

D Calculate train speeds

Sorting arrival and departure times separately allows us to process events in order.

If a train arrives at 10:00 and another departs at 10:05, do we need an extra platform?

A Yes, because arrival is before departure

B No, because departure is after arrival

C No, because the platform is free after departure

D Yes, because trains always need separate platforms

Since the train arrives before the other departs, both trains overlap and need separate platforms.

What does the maximum count of platforms during traversal represent?

A Total departure times

B Total trains

C Maximum train speed

D Minimum platforms needed

The maximum count shows the peak number of trains at the station simultaneously.

Which technique helps track overlapping trains in this problem?

A Hash map lookup

B Two pointers on sorted arrays

C Stack data structure

D Binary search

Two pointers allow simultaneous traversal of arrival and departure arrays to detect overlaps.

What happens when a departure time is less than the next arrival time during traversal?

A Decrease platform count

B Increase platform count

C Keep platform count same

D Reset platform count

A train leaves before the next arrives, freeing a platform, so count decreases.

Explain the step-by-step approach to find the minimum number of platforms needed for trains.

Think about processing train events in order and counting overlaps.

Why is sorting arrival and departure times separately important in this problem?

Consider how sorting helps organize events in time.

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