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

↓

While i < n and j < n

↓

If arrival[i

↓

Increment platforms needed

↓

Move i to next arrival

↓

Update max platforms

Back to While↓

Else

↓

Decrement platforms needed

↓

Move j to next departure

Back to While↓

Return max platforms needed

↩Back to While

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

Execution Sample

DSA C#

int[] arrival = {900, 940, 950, 1100, 1500, 1800};
int[] departure = {910, 1200, 1120, 1130, 1900, 2000};
int n = arrival.Length;
// Find minimum platforms needed

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

Execution Table

Step	Operation	i (arrival index)	j (departure index)	Platforms Needed	Max Platforms	Visual State
1	Start: i=0, j=0	0	0	0	0	[]
2	arrival[0]=900 <= departure[0]=910	0	0	1	1	[Train at 900 arrives, platforms=1]
3	Increment i	1	0	1	1	[Train at 900 on platform]
4	arrival[1]=940 > departure[0]=910	1	0	1	1	[Train at 900 still, departure at 910 pending]
5	Departure at 910, decrement platforms	1	0	0	1	[Train at 900 departed, platforms=0]
6	Increment j	1	1	0	1	[]
7	arrival[1]=940 <= departure[1]=1200	1	1	1	1	[Train at 940 arrives, platforms=1]
8	Increment i	2	1	1	1	[Train at 940 on platform]
9	arrival[2]=950 <= departure[1]=1200	2	1	2	2	[Train at 940 and 950 on platforms]
10	Increment i	3	1	2	2	[Two trains on platforms]
11	arrival[3]=1100 <= departure[1]=1200	3	1	3	3	[Three trains on platforms]
12	Increment i	4	1	3	3	[Three trains on platforms]
13	arrival[4]=1500 > departure[1]=1200	4	1	3	3	[Waiting for departure at 1200]
14	Departure at 1200, decrement platforms	4	1	2	3	[One train left platform]
15	Increment j	4	2	2	3	[Two trains on platforms]
16	arrival[4]=1500 > departure[2]=1120	4	2	2	3	[Waiting for departure at 1120]
17	Departure at 1120, decrement platforms	4	2	1	3	[One train left platform]
18	Increment j	4	3	1	3	[One train on platform]
19	arrival[4]=1500 > departure[3]=1130	4	3	1	3	[Waiting for departure at 1130]
20	Departure at 1130, decrement platforms	4	3	0	3	[No trains on platform]
21	Increment j	4	4	0	3	[]
22	arrival[4]=1500 <= departure[4]=1900	4	4	1	3	[Train at 1500 arrives, platforms=1]
23	Increment i	5	4	1	3	[Train at 1500 on platform]
24	arrival[5]=1800 <= departure[4]=1900	5	4	2	3	[Two trains on platforms]
25	Increment i	6	4	2	3	[Two trains on platforms]
26	i=6 equals n=6, loop ends	6	4	2	3	[Final max platforms=3]

💡 All trains processed, i reached n=6, loop ends

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	After Step 11	After Step 14	After Step 19	After Step 24	Final
i (arrival index)	0	1	1	3	4	4	4	6	6
j (departure index)	0	0	1	1	1	2	3	4	4
Platforms Needed	0	1	0	2	3	2	1	2	2
Max Platforms	0	1	1	2	3	3	3	3	3

Key Moments - 3 Insights

Why do we increment platforms when arrival[i] <= departure[j]?

Because a train arrives before the earliest departure, so we need an extra platform. See execution_table row 2 where platforms increase from 0 to 1.

Why do we decrement platforms when arrival[i] > departure[j]?

Because a train departs before the next arrival, freeing a platform. See execution_table row 5 where platforms decrease from 1 to 0.

Why do we stop when i reaches n, even if j < n?

Because all arrivals are processed, no new trains come, so max platforms needed is final. See execution_table row 26.

Visual Quiz - 3 Questions

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

A 1

B 2

C 3

D 4

💡 Hint

Check the 'Platforms Needed' column at step 11 in execution_table.

At which step does the platforms needed first reach 2?

A Step 7

B Step 9

C Step 14

D Step 19

💡 Hint

Look for the first row where 'Platforms Needed' is 2 in execution_table.

If arrival[3] was 1135 instead of 1100, how would platforms needed change at step 11?

A Platforms needed would be 3

B Platforms needed would be 2

C Platforms needed would be 1

D No change

💡 Hint

Compare arrival[3] with departure[1] at step 11 in execution_table.

Concept Snapshot

Minimum Number of Platforms:
- Sort arrival and departure arrays.
- 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 needed.
- Return max platforms after processing all trains.

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 arrays. 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 during this process. Stop when all trains are processed. This ensures no train waits for a platform.

Practice

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

easy

A. The total time trains spend at the station

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

C. The maximum speed of any train

D. The total number of trains arriving in a day

Solution

1. Step 1: Understand the problem context

   The problem wants to find how many platforms are needed so that no train has to wait for another to leave.

2. Step 2: Identify the key output

   The output is the minimum number of platforms required to handle all trains without delay.

3. Final Answer:

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

4. Quick Check:

   Minimum platforms = no waiting trains [OK]

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

Common Mistakes:

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

2. Which of the following C# code snippets correctly declares arrays for arrival and departure times for the Minimum Number of Platforms problem?

easy

A. int arrival = [900, 940, 950]; int departure = [910, 1200, 1120];

B. int arrival[] = (900, 940, 950); int departure[] = (910, 1200, 1120);

C. int[] arrival = {900, 940, 950}; int[] departure = {910, 1200, 1120};

D. int[] arrival = (900, 940, 950); int[] departure = (910, 1200, 1120);

Solution

1. Step 1: Recall C# array declaration syntax

   In C#, arrays are declared with type[], and values inside curly braces {}.

2. Step 2: Check each option for correct syntax

   int[] arrival = {900, 940, 950}; int[] departure = {910, 1200, 1120}; uses int[] and curly braces {}, which is correct. Others use parentheses or wrong syntax.

3. Final Answer:

   int[] arrival = {900, 940, 950}; int[] departure = {910, 1200, 1120}; -> Option C

4. Quick Check:

   C# arrays use type[] and {} [OK]

Hint: Use int[] and curly braces {} for arrays in C# [OK]

Common Mistakes:

• Using parentheses () instead of curly braces {}
• Declaring arrays without [] after type
• Using square brackets [] for initialization

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

int[] arrival = {900, 940, 950, 1100, 1500, 1800};
int[] departure = {910, 1200, 1120, 1130, 1900, 2000};

int platforms = CalculateMinPlatforms(arrival, departure);
Console.WriteLine(platforms);

// Assume CalculateMinPlatforms correctly implements the algorithm.

medium

A. 5

B. 4

C. 2

D. 3

Solution

1. Step 1: Sort arrival and departure times

   Arrival: 900, 940, 950, 1100, 1500, 1800 Departure: 910, 1120, 1130, 1200, 1900, 2000

2. Step 2: Count overlapping trains to find max platforms

   At 950, trains at 900, 940, 950 overlap (3 trains). Later overlaps are fewer.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Max overlap = 3 platforms [OK]

Hint: Find max overlapping intervals for minimum platforms [OK]

Common Mistakes:

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

4. Identify the error in this C# code snippet for calculating minimum platforms:

int[] arrival = {900, 940, 950};
int[] departure = {910, 1200, 1120};

Array.Sort(arrival);
Array.Sort(departure);

int i = 0, j = 0, platforms = 0, maxPlatforms = 0;
while (i < arrival.Length && j < departure.Length) {
    if (arrival[i] <= departure[j]) {
        platforms++;
        i++;
    } else {
        platforms--;
        j++;
    }
    maxPlatforms = Math.Max(maxPlatforms, platforms);
}
Console.WriteLine(maxPlatforms);

medium

A. The comparison should be 'arrival[i] < departure[j]' instead of '<='

B. The loop condition should be 'i < arrival.Length || j < departure.Length'

C. The arrays should not be sorted before processing

D. The platforms variable should not be incremented

Solution

1. Step 1: Analyze the comparison operator in the loop

   Using '<=' causes counting a train as arriving exactly when another departs, increasing platforms unnecessarily.

2. Step 2: Correct comparison to '<' to avoid overlap at exact departure time

   Changing to '<' means a train arriving at the same time another departs does not increase platform count.

3. Final Answer:

   The comparison should be 'arrival[i] < departure[j]' instead of '<=' -> Option A

4. Quick Check:

   Use '<' to avoid counting simultaneous arrival and departure as overlap [OK]

Hint: Use '<' not '<=' when comparing arrival and departure [OK]

Common Mistakes:

• Using '<=' causes overcounting platforms
• Not sorting arrays before processing
• Incorrect loop condition causing missed trains

5. Given arrival times [900, 940, 950, 1100, 1500, 1800] and departure times [910, 1200, 1120, 1130, 1900, 2000], how would you modify the algorithm to also return the time intervals when the maximum number of platforms are needed?

hard

A. Track intervals when platform count equals max during iteration and store them

B. Return only the maximum platform count without intervals

C. Sort only arrival times and ignore departure times

D. Count total trains without checking overlaps

Solution

1. Step 1: Modify algorithm to track platform count changes

   While iterating, record start time when platforms reach max and end time when count drops.

2. Step 2: Store intervals where platform count equals maximum

   Keep a list of intervals with max platforms to return after processing all times.

3. Final Answer:

   Track intervals when platform count equals max during iteration and store them -> Option A

4. Quick Check:

   Record max platform intervals during count updates [OK]

Hint: Save start/end times when platform count hits max [OK]

Common Mistakes:

• Ignoring time intervals, returning only counts
• Not updating intervals when platform count changes
• Sorting only one array causing wrong intervals