Minimum Number of Platforms in DSA Javascript - Execution Trace

Concept Flow - Minimum Number of Platforms

Sort arrival times

↓

Sort departure times

↓

Initialize pointers i=0, j=0

↓

Compare arrival[i

↓

i

↓

Increment platforms

↓

Move i forward

↩Repeat until i reaches end

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

Execution Sample

DSA Javascript

const arrival = [900, 940, 950, 1100, 1500, 1800];
const departure = [910, 1120, 1130, 1200, 1900, 2000];
// Find minimum platforms needed

This code finds the minimum number of platforms needed for trains given their arrival and departure times.

Execution Table

Step	Operation	i (arrival index)	j (departure index)	Current Platforms	Max Platforms	Action	Visual State
1	Initialize	0	0	0	0	Start with zero platforms	Platforms=0
2	Compare arrival[0]=900 < departure[0]=910	0	0	0	0	Train arrives, need platform	Platforms=1
3	Increment i	1	0	1	1	One platform occupied	Platforms=1
4	Compare arrival[1]=940 < departure[0]=910	1	0	1	1	No, train departs, free platform	Platforms=0
5	Increment j	1	1	0	1	Platform freed	Platforms=0
6	Compare arrival[1]=940 < departure[1]=1120	1	1	0	1	Train arrives, need platform	Platforms=1
7	Increment i	2	1	1	1	One platform occupied	Platforms=1
8	Compare arrival[2]=950 < departure[1]=1120	2	1	1	1	Train arrives, need another platform	Platforms=2
9	Increment i	3	1	2	2	Two platforms occupied	Platforms=2
10	Compare arrival[3]=1100 < departure[1]=1120	3	1	2	2	Train arrives, need another platform	Platforms=3
11	Increment i	4	1	3	3	Three platforms occupied	Platforms=3
12	Compare arrival[4]=1500 < departure[1]=1120	4	1	3	3	No, train departs, free platform	Platforms=2
13	Increment j	4	2	2	3	Platform freed	Platforms=2
14	Compare arrival[4]=1500 < departure[2]=1130	4	2	2	3	No, train departs, free platform	Platforms=1
15	Increment j	4	3	1	3	Platform freed	Platforms=1
16	Compare arrival[4]=1500 < departure[3]=1200	4	3	1	3	No, train departs, free platform	Platforms=0
17	Increment j	4	4	0	3	Platform freed	Platforms=0
18	Compare arrival[4]=1500 < departure[4]=1900	4	4	0	3	Train arrives, need platform	Platforms=1
19	Increment i	5	4	1	3	One platform occupied	Platforms=1
20	Compare arrival[5]=1800 < departure[4]=1900	5	4	1	3	Train arrives, need another platform	Platforms=2
21	Increment i	6	4	2	3	Two platforms occupied	Platforms=2
22	i reached end	6	4	2	3	All trains processed	Final max platforms=3

💡 i reached length of arrival array, all trains processed

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 8	After Step 11	After Step 16	After Step 21	Final
i (arrival index)	0	1	1	3	4	4	6	6
j (departure index)	0	0	1	1	1	4	4	4
Current Platforms	0	1	0	2	3	0	2	2
Max Platforms	0	1	1	2	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 departs before or at the arrival of the next train, a platform frees up, so we move 'j' forward to consider the next departure. This is shown in steps 4, 12, 14, 16 where platforms decrease.

Why do we keep track of 'max platforms' separately from 'current platforms'?

Because 'current platforms' changes as trains arrive and depart, but we want to know the highest number of platforms needed at any time. This is updated in steps 2, 8, 11 where max platforms increase.

What happens if arrival and departure arrays are not sorted?

The logic fails because we rely on sorted times to correctly count overlapping trains. Sorting is done at the start (concept flow) to ensure correct platform counting.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'Current Platforms' at step 10?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Current Platforms' column at step 10 in the execution table.

At which step does the 'Max Platforms' first reach 3?

A Step 8

B Step 11

C Step 16

D Step 21

💡 Hint

Look at the 'Max Platforms' column and find when it changes to 3 for the first time.

If the arrival array was not sorted, how would the execution table change?

A The platform count might be incorrect due to wrong order of arrivals.

B The departure pointer 'j' would increment faster.

C The max platforms would always be 1.

D The algorithm would run faster.

💡 Hint

Refer to the key moment about sorting and its importance in the logic.

Concept Snapshot

Minimum Number of Platforms:
- Sort arrival and departure times separately.
- Use two pointers i, j starting at 0.
- If arrival[i] < departure[j], increment platforms and i.
- Else decrement platforms and increment j.
- Track max platforms during process.
- Result is max platforms needed at once.

Full Transcript

To find the minimum number of platforms needed for trains, first sort the arrival and departure times. Then use two pointers to traverse both arrays. When a train arrives before the earliest departure, increase the platform count. When a train departs before or at the next arrival, decrease the platform count. Keep track of the maximum platforms needed during this process. The final maximum is the minimum number of platforms required. Sorting is essential to correctly count overlapping trains. This method efficiently counts platforms by comparing arrival and departure times step-by-step.

Practice

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

easy

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

B. The total number of trains arriving in a day

C. The longest time a train stays on a platform

D. The earliest train arrival time

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 simultaneously for overlapping train times, not total trains or times.

3. Final Answer:

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

4. Quick Check:

   Minimum platforms = least needed to avoid waiting [OK]

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

Common Mistakes:

• Confusing total trains with platforms needed
• Thinking about train durations instead of overlaps
• Ignoring simultaneous arrivals and departures

2. Which of the following JavaScript code snippets correctly sorts an array of train arrival times stored as numbers?

easy

A. arrivals.sort()

B. arrivals.sort((a, b) => a - b)

C. arrivals.sort((a, b) => b - a)

D. arrivals.sort((a, b) => a + b)

Solution

1. Step 1: Understand JavaScript sort behavior

   By default, sort() converts elements to strings and sorts lexicographically, which is incorrect for numbers.

2. Step 2: Use numeric comparison function

   Using (a, b) => a - b sorts numbers in ascending order correctly.

3. Final Answer:

   arrivals.sort((a, b) => a - b) -> Option B

4. Quick Check:

   Numeric sort uses (a, b) => a - b [OK]

Hint: Use numeric compare (a, b) => a - b to sort numbers [OK]

Common Mistakes:

• Using sort() without compare function for numbers
• Using incorrect compare functions like a + b
• Sorting in descending order when ascending needed

3. What is the minimum number of platforms needed for trains with arrival times [900, 940, 950, 1100, 1500, 1800] and departure times [910, 1200, 1120, 1130, 1900, 2000]?

medium

A. 4

B. 2

C. 1

D. 3

Solution

1. Step 1: Sort arrival and departure times

   Arrivals: 900, 940, 950, 1100, 1500, 1800; Departures: 910, 1120, 1130, 1200, 1900, 2000.

2. Step 2: Count platforms needed by comparing arrivals and departures

   At 900 arrival, platform count=1; 940 arrival before 910 departure? No, so platform count=1; 950 arrival before 1120 departure? Yes, platform count=2; 1100 arrival before 1120 departure? Yes, platform count=3; Then departures reduce count as trains leave.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Max overlapping trains = 3 platforms needed [OK]

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

Common Mistakes:

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

4. Identify the error in this JavaScript snippet for calculating minimum platforms:

let i = 0, j = 0, platforms = 0, maxPlatforms = 0;
arrivals.sort();
departures.sort();
while (i < arrivals.length && j < departures.length) {
  if (arrivals[i] <= departures[j]) {
    platforms++;
    i++;
    if (platforms > maxPlatforms) maxPlatforms = platforms;
  } else {
    platforms--;
    j++;
  }
}
return maxPlatforms;

medium

A. Using <= instead of < in if condition

B. Incrementing i and j in wrong order

C. Sorting arrays without numeric compare function

D. Not initializing maxPlatforms to arrivals.length

Solution

1. Step 1: Check sorting method

   arrivals.sort() and departures.sort() sort lexicographically by default, causing wrong order for numbers.

2. Step 2: Correct sorting for numeric arrays

   Use arrivals.sort((a,b) => a - b) and departures.sort((a,b) => a - b) to sort numbers properly.

3. Final Answer:

   Sorting arrays without numeric compare function -> Option C

4. Quick Check:

   Numeric sort needs compare function [OK]

Hint: Always use numeric compare in sort for numbers [OK]

Common Mistakes:

• Sorting numbers as strings causing wrong order
• Confusing comparison operators in if condition
• Incorrect loop increments

5. Given arrival times [1000, 1010, 1025, 1030, 1040] and departure times [1020, 1035, 1045, 1050, 1100], what is the minimum number of platforms needed if trains can arrive and depart at the same time without conflict?

hard

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Sort arrival and departure times

   Arrivals: 1000, 1010, 1025, 1030, 1040; Departures: 1020, 1035, 1045, 1050, 1100.

2. Step 2: Count platforms considering arrival == departure means no conflict

   Compare arrivals and departures with condition arrivals[i] < departures[j] (strict less than). Counting overlaps: at 1000 arrival platform=1; 1010 arrival platform=2; 1025 arrival platform=3; 1020 departure reduces platform to 2; 1030 arrival platform=3; 1035 departure reduces to 2; 1040 arrival platform=3; then departures reduce count.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Strict less than counts simultaneous arrival/departure correctly [OK]

Hint: Use strict < to handle same-time arrival and departure [OK]

Common Mistakes:

• Using <= causing extra platform count
• Not sorting times before counting
• Ignoring simultaneous arrival and departure rule