Minimum Number of Platforms in DSA Typescript - 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

↓

Update max platforms

↓

Repeat until all trains processed

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

Execution Sample

DSA Typescript

const arrival = [900, 940, 950, 1100, 1500, 1800];
const departure = [910, 1200, 1120, 1130, 1900, 2000];
// 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)	Current Platforms	Max Platforms	Visual State
1	Compare arrival[0]=900 and departure[0]=910	0	0	1	1	Platforms: 1 (Train at 900 arrived)
2	arrival[1]=940 < departure[0]=910? No, departure[0] < arrival[1]	1	0	0	1	Platforms: 0 (Train at 900 departed)
3	Move j to 1	1	1	0	1	Platforms: 0
4	Compare arrival[1]=940 and departure[1]=1200	1	1	1	1	Platforms: 1 (Train at 940 arrived)
5	Compare arrival[2]=950 and departure[1]=1200	2	1	2	2	Platforms: 2 (Train at 950 arrived)
6	Compare arrival[3]=1100 and departure[1]=1200	3	1	3	3	Platforms: 3 (Train at 1100 arrived)
7	Compare arrival[4]=1500 and departure[1]=1200	4	1	2	3	Platforms: 2 (Train at 1200 departed)
8	Move j to 2	4	2	2	3	Platforms: 2
9	Compare arrival[4]=1500 and departure[2]=1120	4	2	1	3	Platforms: 1 (Train at 1120 departed)
10	Move j to 3	4	3	1	3	Platforms: 1
11	Compare arrival[4]=1500 and departure[3]=1130	4	3	0	3	Platforms: 0 (Train at 1130 departed)
12	Move j to 4	4	4	0	3	Platforms: 0
13	Compare arrival[4]=1500 and departure[4]=1900	4	4	1	3	Platforms: 1 (Train at 1500 arrived)
14	Compare arrival[5]=1800 and departure[4]=1900	5	4	2	3	Platforms: 2 (Train at 1800 arrived)
15	Compare arrival[6]=undefined and departure[4]=1900	6	4	2	3	No more arrivals, process departures
16	Move j to 5	6	5	1	3	Platforms: 1 (Train at 1900 departed)
17	Move j to 6	6	6	0	3	Platforms: 0 (Train at 2000 departed)
18	End	6	6	0	3	All trains processed

💡 All trains processed: i and j pointers reached end of arrival and departure arrays.

Variable Tracker

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

Key Moments - 3 Insights

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

Because a train has left before the next train arrives, so one platform is freed. See execution_table steps 2, 7, 9.

Why do we update max platforms only when arrival[i] < departure[j]?

Because a new train arrives before any train leaves, increasing platform need. See execution_table steps 1, 5, 6.

What happens when all arrivals are processed but departures remain?

We keep moving the departure pointer to free platforms until all trains have left. See execution_table steps 15-17.

Visual Quiz - 3 Questions

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

A 1

B 2

C 3

D 0

💡 Hint

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

At which step does the number of platforms first decrease from 3 to 2?

A Step 7

B Step 5

C Step 10

D Step 2

💡 Hint

Look for when 'Current Platforms' changes from 3 to 2 in execution_table.

If arrival[2] was 1300 instead of 950, how would max platforms change?

A Max platforms would increase

B Max platforms would decrease

C Max platforms would stay the same

D Cannot determine

💡 Hint

Consider how later arrival affects overlapping trains and platform count in variable_tracker.

Concept Snapshot

Minimum Number of Platforms:
- Sort arrival and departure times separately.
- Use two pointers i, j for arrivals and departures.
- Increment platforms if arrival[i] < departure[j].
- Decrement platforms if departure[j] <= arrival[i].
- Track max platforms needed during traversal.

Full Transcript

To find the minimum number of platforms needed for trains, first sort the arrival and departure times. Then use two pointers to compare the next arrival and departure. If a train arrives before the earliest departure, increase platform count. If a train departs before the next arrival, decrease platform count. Keep track of the maximum platforms needed at any time. Continue until all trains are processed. This ensures no train waits for a platform.