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.