Minimum Number of Platforms in DSA C++ - Execution Trace

Concept Flow - Minimum Number of Platforms

Sort arrival times

↓

Sort departure times

↓

Initialize pointers i=0, j=0

↓

Compare arrival[i

↓

Increment platforms

↓

Move i or j pointer

↓

Repeat until all trains processed

↓

Return max platforms needed

Sort arrival and departure times, then use two pointers to count platforms needed by comparing arrivals and departures.

Execution Sample

DSA C++

arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1200, 1120, 1130, 1900, 2000]

// Find minimum platforms needed

Given arrival and departure times, find the minimum number of platforms needed so no train waits.

Execution Table

Step	Operation	i (arrival index)	j (departure index)	Current Platforms	Max Platforms	Visual State (Platforms)
1	Start with i=0, j=0	0	0	0	0	[]
2	arr[0]=900 <= dep[0]=910, train arrives	0	0	1	1	[Train1]
3	Move i to 1	1	0	1	1	[Train1]
4	arr[1]=940 > dep[0]=910, train departs	1	0	0	1	[]
5	Move j to 1	1	1	0	1	[]
6	arr[1]=940 <= dep[1]=1200, train arrives	1	1	1	1	[Train2]
7	Move i to 2	2	1	1	1	[Train2]
8	arr[2]=950 <= dep[1]=1200, train arrives	2	1	2	2	[Train2, Train3]
9	Move i to 3	3	1	2	2	[Train2, Train3]
10	arr[3]=1100 <= dep[1]=1200, train arrives	3	1	3	3	[Train2, Train3, Train4]
11	Move i to 4	4	1	3	3	[Train2, Train3, Train4]
12	arr[4]=1500 > dep[1]=1200, train departs	4	1	2	3	[Train3, Train4]
13	Move j to 2	4	2	2	3	[Train3, Train4]
14	arr[4]=1500 > dep[2]=1120, train departs	4	2	1	3	[Train4]
15	Move j to 3	4	3	1	3	[Train4]
16	arr[4]=1500 > dep[3]=1130, train departs	4	3	0	3	[]
17	Move j to 4	4	4	0	3	[]
18	arr[4]=1500 <= dep[4]=1900, train arrives	4	4	1	3	[Train5]
19	Move i to 5	5	4	1	3	[Train5]
20	arr[5]=1800 <= dep[4]=1900, train arrives	5	4	2	3	[Train5, Train6]
21	Move i to 6	6	4	2	3	[Train5, Train6]
22	No more arrivals, trains depart	6	4	2	3	[Train5, Train6]
23	Move j to 5	6	5	1	3	[Train6]
24	Move j to 6	6	6	0	3	[]
25	All trains processed	6	6	0	3	[]

💡 All trains processed, max platforms needed is 3

Variable Tracker

Variable	Start	After Step 2	After Step 8	After Step 10	After Step 12	After Step 18	After Step 20	Final
i (arrival index)	0	1	3	4	4	5	6	6
j (departure index)	0	0	1	1	2	4	4	6
Current Platforms	0	1	2	3	2	1	2	0
Max Platforms	0	1	2	3	3	3	3	3

Key Moments - 3 Insights

Why do we increment platforms when arrival time is less or equal to departure time?

Because a train arrives before the previous one departs, so we need an extra platform. See steps 2, 8, and 10 in execution_table where platforms increase.

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

Because a train departs before the next arrives, freeing a platform. See steps 4, 12, and 14 where platforms decrease.

Why do we keep track of max platforms separately?

Because current platforms can go up and down, but max platforms records the highest number needed at any time. See variable_tracker 'Max Platforms' row.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, how many platforms are currently needed?

A 1

B 2

C 3

D 4

💡 Hint

Check the 'Current Platforms' column at step 10 in execution_table.

At which step does the condition arr[i] > dep[j] first become true?

A Step 4

B Step 8

C Step 12

D Step 14

💡 Hint

Look for the first step where platforms decrease due to departure before arrival.

If the arrival time at index 3 was 1300 instead of 1100, how would max platforms change?

A Remain 3

B Decrease to 2

C Increase to 4

D Become 1

💡 Hint

Consider how arrival and departure times overlap and check max platforms in variable_tracker.

Concept Snapshot

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

Full Transcript

To find the minimum number of platforms needed for trains, first sort the arrival and departure times. Use two pointers to traverse both lists. When a train arrives before the earliest departure, increase the platform count. When a train departs before the next arrival, decrease the platform count. Keep track of the maximum platforms needed at any point. This ensures no train waits for a platform.

Practice

1. What does the "Minimum Number of Platforms" problem primarily ask you to find?

easy

A. The total number of trains passing through the station

B. The maximum number of trains arriving at the station

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

D. The shortest time a train stays on a platform

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum platforms so that no train waits due to platform unavailability.

2. Step 2: Clarify what is being counted

   We count platforms needed to handle overlapping train schedules without delay.

3. Final Answer:

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

4. Quick Check:

   Minimum platforms = no waiting trains [OK]

Hint: Focus on overlapping train times to find platform count [OK]

Common Mistakes:

• Confusing total trains with platforms needed
• Ignoring overlapping arrival and departure times
• Thinking about train speed or distance

2. Which of the following C++ code snippets correctly declares vectors to store arrival and departure times for the Minimum Number of Platforms problem?

easy

A. vector<int> arrival; vector<int> departure;

B. vector arrival, departure int;

C. std::vector arrival(int), departure(int);

D. std::vector<int> arrival, departure;

Solution

1. Step 1: Check correct vector syntax in C++

   Vectors must be declared with type inside angle brackets and variable names, e.g., vector<int> arrival;

2. Step 2: Identify valid declarations

   vector<int> arrival; vector<int> departure; uses correct syntax for two separate vectors: vector<int> arrival; vector<int> departure;

3. Final Answer:

   vector<int> arrival; vector<int> departure; -> Option A

4. Quick Check:

   Correct vector syntax = vector<int> arrival; vector<int> departure; [OK]

Hint: Use vector<int> name; for integer vectors in C++ [OK]

Common Mistakes:

• Missing angle brackets <> for vector type
• Incorrect order of type and variable name
• Using wrong syntax like vector arrival(int)

3. Consider the following C++ code snippet for Minimum Number of Platforms problem:

std::vector<int> arrival = {900, 940, 950, 1100, 1500, 1800};
std::vector<int> departure = {910, 1200, 1120, 1130, 1900, 2000};

int platforms = 1, result = 1;
int i = 1, j = 0;

while (i < arrival.size() && j < departure.size()) {
  if (arrival[i] <= departure[j]) {
    platforms++;
    i++;
  } else {
    platforms--;
    j++;
  }
  if (platforms > result) result = platforms;
}

std::cout << result << std::endl;

What is the output of this code?

medium

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace arrival and departure comparisons

   Compare arrival[i] and departure[j]: - i=1(940) <= j=0(910)? No, so platforms-- (1->0), j=1 - i=1(940) <= j=1(1200)? Yes, platforms++ (0->1), i=2 - i=2(950) <= j=1(1200)? Yes, platforms++ (1->2), i=3 - i=3(1100) <= j=1(1200)? Yes, platforms++ (2->3), i=4 - i=4(1500) <= j=1(1200)? No, platforms-- (3->2), j=2 - i=4(1500) <= j=2(1120)? No, platforms-- (2->1), j=3 - i=4(1500) <= j=3(1130)? No, platforms-- (1->0), j=4 - i=4(1500) <= j=4(1900)? Yes, platforms++ (0->1), i=5 - i=5(1800) <= j=4(1900)? Yes, platforms++ (1->2), i=6 (end)

2. Step 2: Find maximum platforms during process

   Maximum platforms reached is 3 during the steps.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Max overlapping trains = 3 [OK]

Hint: Count overlaps by comparing sorted arrivals and departures [OK]

Common Mistakes:

• Not updating platform count correctly
• Mixing up arrival and departure indices
• Assuming max platforms equals total trains

4. The following code snippet is intended to find the minimum number of platforms needed. Identify the bug:

std::vector<int> arrival = {900, 940, 950, 1100};
std::vector<int> departure = {910, 1120, 1130, 1200};

int platforms = 1, result = 1;
int i = 1, j = 0;

while (i < arrival.size() && j < departure.size()) {
  if (arrival[i] < departure[j]) {
    platforms++;
    i++;
  } else {
    platforms--;
    j++;
  }
  if (platforms > result) result = platforms;
}

std::cout << result << std::endl;

medium

A. The comparison should be <= instead of < in if condition

B. The initial value of platforms should be 0, not 1

C. The vectors arrival and departure are not sorted

D. The loop condition should use || instead of &&

Solution

1. Step 1: Analyze the if condition for arrival and departure

   The condition uses arrival[i] < departure[j], but trains arriving exactly when another departs need a platform, so <= is correct.

2. Step 2: Understand impact of using < instead of <=

   Using < misses cases where arrival equals departure, causing undercount of platforms needed.

3. Final Answer:

   The comparison should be <= instead of < in if condition -> Option A

4. Quick Check:

   Use <= to count overlapping trains correctly [OK]

Hint: Use <= to include trains arriving exactly at departure time [OK]

Common Mistakes:

• Using < instead of <= causes wrong platform count
• Not sorting arrival and departure arrays
• Incorrect loop condition with && vs ||

5. You have the following train schedules:

Arrival: {1000, 1010, 1025, 1030, 1040}
Departure: {1015, 1020, 1035, 1045, 1050}

What is the minimum number of platforms required so that no train waits? Choose the correct approach and answer.

hard

A. Sort only arrival times and count unique values; answer is 4

B. Count total trains; answer is 5

C. Use a hash map to count trains per time; answer is 2

D. Sort both arrays, then use two pointers to count overlaps; answer is 2

Solution

1. Step 1: Sort arrival and departure times

   Both arrays are already sorted: arrival = {1000,1010,1025,1030,1040}, departure = {1015,1020,1035,1045,1050}

2. Step 2: Use two pointers to count overlapping trains

   Compare arrival[i] and departure[j]: - 1010 <= 1015: platforms=2 - 1025 <= 1015? No, platforms=1 - 1025 <= 1020? No, platforms=0 - 1025 <= 1035? Yes, platforms=1 - 1030 <= 1035? Yes, platforms=2 - 1040 <= 1035? No, platforms=1 - 1040 <= 1045? Yes, platforms=2 Maximum platforms needed = 2 during overlaps.

3. Final Answer:

   Sort both arrays, then use two pointers to count overlaps; answer is 2 -> Option D

4. Quick Check:

   Two pointer overlap count = 2 platforms [OK]

Hint: Sort arrivals and departures, count overlaps with two pointers [OK]

Common Mistakes:

• Counting total trains instead of overlaps
• Not sorting both arrays
• Using incorrect data structures like hash maps unnecessarily