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

↓

Track max platforms needed

↓

Repeat until all trains processed

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

Execution Sample

DSA C

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

Calculates minimum platforms needed by sorting times and counting overlaps.

Execution Table

Step	Operation	i (arrival index)	j (departure index)	Platforms Count	Max Platforms	Visual State (Arrivals vs Departures)
1	Sort arrival and departure arrays	0	0	0	0	Arrivals: [900, 940, 950, 1100, 1500, 1800] Departures: [910, 1120, 1130, 1200, 1900, 2000]
2	Compare arr[0]=900 <= dep[0]=910	0	0	1	1	Platform needed for train arriving at 900
3	Increment i to 1	1	0	1	1	Platforms still 1
4	Compare arr[1]=940 <= dep[0]=910	1	0	0	1	Train at 940 arrives after 910 departure, platform freed
5	Increment j to 1	1	1	0	1	Platforms now 0
6	Compare arr[1]=940 <= dep[1]=1120	1	1	1	1	New train arrives before next departure, platform needed
7	Increment i to 2	2	1	1	1	Platforms 1
8	Compare arr[2]=950 <= dep[1]=1120	2	1	2	2	Another train arrives, platform count increases
9	Increment i to 3	3	1	2	2	Platforms 2
10	Compare arr[3]=1100 <= dep[1]=1120	3	1	3	3	Third train overlaps, platform count 3
11	Increment i to 4	4	1	3	3	Platforms 3
12	Compare arr[4]=1500 <= dep[1]=1120	4	1	2	3	Train arrives after departure, platform freed
13	Increment j to 2	4	2	2	3	Platforms 2
14	Compare arr[4]=1500 <= dep[2]=1130	4	2	1	3	Another departure frees platform
15	Increment j to 3	4	3	1	3	Platforms 1
16	Compare arr[4]=1500 <= dep[3]=1200	4	3	0	3	Departure frees platform
17	Increment j to 4	4	4	0	3	Platforms 0
18	Compare arr[4]=1500 <= dep[4]=1900	4	4	1	3	Train arrives before departure, platform needed
19	Increment i to 5	5	4	1	3	Platforms 1
20	Compare arr[5]=1800 <= dep[4]=1900	5	4	2	3	Another train arrives, platform count 2
21	Increment i to 6	6	4	2	3	Platforms 2
22	i reached n=6, loop ends	6	4	2	3	All trains processed
23	Return maxPlatforms	-	-	-	3	Minimum platforms needed is 3

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

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	After Step 18	After Step 20	Final
i	0	1	1	2	3	4	4	5	6	6
j	0	0	1	1	1	1	2	4	4	4
platforms	0	1	0	1	2	3	2	1	2	2
maxPlatforms	0	1	1	1	2	3	3	3	3	3

Key Moments - 3 Insights

Why do we increment 'j' (departure pointer) only when arrival[i] > departure[j]?

Because when a train arrives after another departs, a platform frees up, so we move the departure pointer to check next departure. This is shown in execution_table steps 4, 12, and 16 where platforms decrease and j increments.

Why do we track maxPlatforms separately from current platforms?

Current platforms count changes as trains arrive and depart, but maxPlatforms keeps the highest number seen so far. This ensures we know the maximum platforms needed at any time, as seen in steps 10 and 20.

What happens if arrival and departure times are equal?

If arrival[i] == departure[j], we treat it as arrival <= departure, so platforms increase. This ensures a platform is ready for the arriving train, as in step 2.

Visual Quiz - 3 Questions

Look at the execution_table, what is the platforms count at step 10?

A 1

B 2

C 3

D 0

💡 Hint

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

At which step does the departure pointer 'j' first increment?

A Step 5

B Step 3

C Step 7

D Step 9

💡 Hint

Look for the first step where 'j' changes from 0 to 1 in variable_tracker.

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

A It would increase to 1

B It would remain 0

C It would decrease to -1

D It would increase to 2

💡 Hint

Compare arrival[1] with departure[0] at step 4 in execution_table and consider the condition arr[i] <= dep[j].

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 increment 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, we first sort the arrival and departure times. We use two pointers: one for arrivals and one for departures. We compare the current arrival time with the current departure time. If the arrival is earlier or equal, it means a train needs a platform, so we increase the platform count and move to the next arrival. If the arrival is later, it means a train has left, freeing a platform, so we decrease the platform count and move to the next departure. We keep track of the maximum number of platforms needed at any time. When all trains are processed, this maximum is the minimum number of platforms required to avoid waiting.

Practice

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

easy

A. The earliest train arrival time

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

C. The total number of trains arriving in a day

D. The maximum number of trains arriving at the same 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, which determines how many platforms are needed simultaneously.

3. Final Answer:

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

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 only arrivals or departures

2. Which of the following C code snippets correctly declares arrays for train arrival and departure times for 5 trains?

easy

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

B. int arrival = {900, 940, 950, 1100, 1500}; int departure = {910, 1200, 1120, 1130, 1900};

C. int arrival[5] = (900, 940, 950, 1100, 1500); int departure[5] = (910, 1200, 1120, 1130, 1900);

D. int arrival[] = 900, 940, 950, 1100, 1500; int departure[] = 910, 1200, 1120, 1130, 1900;

Solution

1. Step 1: Check array declaration syntax in C

   Arrays must be declared with size or empty brackets and initialized with curly braces {}.

2. Step 2: Validate each option

   int arrival[5] = {900, 940, 950, 1100, 1500}; int departure[5] = {910, 1200, 1120, 1130, 1900}; uses correct syntax with size and braces. Others use incorrect syntax like parentheses or missing braces.

3. Final Answer:

   int arrival[5] = {900, 940, 950, 1100, 1500}; int departure[5] = {910, 1200, 1120, 1130, 1900}; -> Option A

4. Quick Check:

   Arrays use {} with size or empty brackets [OK]

Hint: Use curly braces {} to initialize arrays in C [OK]

Common Mistakes:

• Using parentheses () instead of braces {}
• Missing array size or empty brackets
• Assigning values without braces

3. Given arrival times {900, 940, 950, 1100, 1500} and departure times {910, 1200, 1120, 1130, 1900}, what is the minimum number of platforms needed? Consider the following code snippet:

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

// Assume arrays are sorted
int i = 1, j = 0, platforms = 1, result = 1;
while (i < n && j < n) {
  if (arrival[i] <= departure[j]) {
    platforms++;
    i++;
    if (platforms > result) result = platforms;
  } else {
    platforms--;
    j++;
  }
}
printf("%d", result);

medium

A. 4

B. 2

C. 1

D. 3

Solution

1. Step 1: Trace the platform count with given times

   Starts platforms=1 (900 arrival), i=1, j=0. 940 <= 910? No, so platforms--, j=1. Then 940 <= 1200: platforms++, i=2. 950 <= 1200: platforms++, i=3. 1100 <= 1200: platforms++, i=4 (max=3). Later departures reduce platforms.

2. Step 2: Find max platforms during iteration

   Maximum platforms reached is 3 (trains 940-1200, 950-1120, 1100-1130 overlap).

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Max overlapping trains = 3 [OK]

Hint: Sort times and count overlaps to find max platforms [OK]

Common Mistakes:

• Not sorting arrival and departure arrays
• Incorrectly incrementing or decrementing platform count
• Confusing <= with < in comparisons

4. Identify the error in the following code snippet for calculating minimum platforms:

int arrival[] = {900, 940, 950, 1100, 1500};
int departure[] = {910, 1200, 1120, 1130, 1900};
int n = 5;
int i = 0, j = 0, platforms = 0, result = 0;
while (i < n && j < n) {
  if (arrival[i] < departure[j]) {
    platforms++;
    i++;
    if (platforms > result) result = platforms;
  } else {
    platforms--;
    j++;
  }
}
printf("%d", result);

medium

A. No error, code is correct

B. Initialization of platforms should start at 1

C. Loop condition should be i <= n && j <= n

D. Comparison should be arrival[i] <= departure[j]

Solution

1. Step 1: Verify initialization and first steps

   platforms=0, i=0, j=0 correct. 900 < 910: platforms=1, i=1, result=1.

2. Step 2: Check logic and trace

   940 < 910? No: platforms=0, j=1. Then 940 < 1200: platforms=1, i=2; 950<1200:2, i=3; 1100<1200:3, i=4 (max=3). Continues correctly. < handles equal times optimally.

3. Final Answer:

   No error, code is correct -> Option A

4. Quick Check:

   Code outputs 3, matching overlaps [OK]

Hint: plat=0, i=0,j=0, if arr[i] < dep[j] correctly minimizes platforms [OK]

Common Mistakes:

• Using arrival[i] <= departure[j] (overcounts on equal times)
• Initializing platforms=1 with i=0 (overcounts first arrival)
• Loop i <= n && j <= n (off-by-one)

5. You have arrival times {900, 940, 950, 1100, 1500, 1800} and departure times {910, 1200, 1120, 1130, 1900, 2000}. How would you modify the algorithm to handle trains arriving and departing at the same time (e.g., arrival[i] == departure[j]) to minimize platforms needed?

hard

A. Ignore trains with equal arrival and departure times

B. Treat arrival[i] == departure[j] as arrival first to allocate platform

C. Treat arrival[i] == departure[j] as departure first to free platform

D. Increase platform count by 2 when times are equal

Solution

1. Step 1: Understand impact of equal arrival and departure times

   If a train departs at the same time another arrives, the platform can be reused without adding a new one.

2. Step 2: Adjust comparison logic

   When arrival[i] == departure[j], count departure first to free platform before arrival increments platform count.

3. Final Answer:

   Treat arrival[i] == departure[j] as departure first to free platform -> Option C

4. Quick Check:

   Departure before arrival frees platform [OK]

Hint: Count departures before arrivals when times are equal [OK]

Common Mistakes:

• Counting arrival before departure causing extra platform
• Ignoring equal times leading to wrong count
• Adding platforms unnecessarily