Minimum Number of Platforms in DSA Java - Execution Trace

Concept Flow - Minimum Number of Platforms

Sort arrival times

↓

Sort departure times

↓

Initialize pointers i=0, j=0

↓

Compare arrival[i

↓

Increment platform count

↓

Update max platforms

↓

Move pointers i or j

↓

Repeat until all trains processed

↓

Return max platforms needed

We sort arrival and departure times, then use two pointers to track platforms needed by comparing arrivals and departures step-by-step.

Execution Sample

DSA Java

int findPlatform(int[] arr, int[] dep) {
  Arrays.sort(arr);
  Arrays.sort(dep);
  int platform = 0, maxPlatform = 0;
  int i = 0, j = 0;
  while (i < arr.length && j < dep.length) {
    if (arr[i] <= dep[j]) {
      platform++;
      i++;
    } else {
      platform--;
      j++;
    }
    maxPlatform = Math.max(maxPlatform, platform);
  }
  return maxPlatform;
}

This code finds the minimum number of platforms needed so that no train waits.

Execution Table

Step	Operation	i (arrival index)	j (departure index)	Platform Count	Max Platforms	Action	Visual State (Platforms)
1	Compare arr[0]=900 <= dep[0]=910	0	0	1	1	Increment platform, move i	Platform count: 1
2	Compare arr[1]=940 <= dep[0]=910	1	0	0	1	Decrement platform, move j	Platform count: 0
3	Compare arr[1]=940 <= dep[1]=1200	1	1	1	1	Increment platform, move i	Platform count: 1
4	Compare arr[2]=950 <= dep[1]=1200	2	1	2	2	Increment platform, move i	Platform count: 2
5	Compare arr[3]=1100 <= dep[1]=1200	3	1	3	3	Increment platform, move i	Platform count: 3
6	Compare arr[4]=1500 <= dep[1]=1200	4	1	2	3	Decrement platform, move j	Platform count: 2
7	Compare arr[4]=1500 <= dep[2]=1900	4	2	3	3	Increment platform, move i	Platform count: 3
8	Compare i=5 (end) or j=2	5	2	3	3	End loop	Final max platforms: 3

💡 All trains processed; max platforms needed is 3

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
i (arrival index)	0	1	1	2	3	4	4	5	5
j (departure index)	0	0	1	1	1	1	2	2	2
platform (current)	0	1	0	1	2	3	2	3	3
maxPlatform	0	1	1	1	2	3	3	3	3

Key Moments - 3 Insights

Why do we increment platform count when arrival time is equal to departure time?

Because a train arriving exactly when another departs still needs a platform until the departure happens, so we count the arrival first as shown in steps 1 and 3 where arr[i] <= dep[j] leads to increment.

Why do we decrement platform count when arrival time is greater than departure time?

Because a train has left before the next arrives, freeing a platform. This is shown in step 2 and 6 where arr[i] > dep[j] causes platform to decrement and pointer j to move.

Why do we sort arrival and departure times separately?

Sorting allows us to process events in chronological order independently, so we can compare arrivals and departures step-by-step to track platform usage accurately, as seen in the initial setup before step 1.

Visual Quiz - 3 Questions

Look at the execution table, what is the platform count after step 4?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Platform Count' column at step 4 in the execution table.

At which step does the platform count first reach 3?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Platform Count' and 'Max Platforms' columns to find when platform count hits 3.

If the arrival time at index 1 was 920 instead of 940, how would the platform count change at step 2?

A It would increment instead of decrement

B It would decrement as before

C It would stay the same

D It would cause an error

💡 Hint

Compare arr[1] with dep[0] at step 2 in the execution table and consider the condition arr[i] <= dep[j].

Concept Snapshot

Minimum Number of Platforms:
- Sort arrival and departure arrays separately
- Use two pointers i, j for arrivals and departures
- If arrival[i] <= departure[j], increment platform count and move i
- Else decrement platform count and move j
- Track max platform count during iteration
- Result is max platforms needed to avoid waiting

Full Transcript

To find the minimum number of platforms needed for trains arriving and departing, we first sort the arrival and departure times separately. We then use two pointers to iterate through these sorted arrays. At each step, if the next train arrives before or exactly when another departs, we increase the platform count because a platform is needed. If a train departs before the next arrives, we decrease the platform count as a platform is freed. We keep track of the maximum platform count during this process. The maximum count found is the minimum number of platforms required so that no train waits. This approach efficiently handles overlapping train schedules by comparing arrival and departure times in order.

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