Minimum Number of Platforms in DSA Javascript

Mental Model

We want to find the smallest number of train platforms needed so no train waits. We do this by checking how many trains overlap in time.

Analogy: Imagine a parking lot where cars arrive and leave at different times. The minimum number of parking spots needed is the maximum number of cars parked at the same time.

Arrivals:  9:00  9:40  9:50  11:00  15:00  18:00
Departures: 9:10  12:00  11:20  11:30  19:00  20:00
Platforms needed: max overlap of arrival and departure times

Dry Run Walkthrough

Input: arrivals: [900, 940, 950, 1100, 1500, 1800], departures: [910, 1200, 1120, 1130, 1900, 2000]

Goal: Find the minimum number of platforms needed so that no train waits.

Step 1: Sort arrivals and departures separately

arrivals: [900, 940, 950, 1100, 1500, 1800]
departures: [910, 1120, 1130, 1200, 1900, 2000]

Why: Sorting helps us process events in chronological order.

Step 2: Initialize pointers i=0 (arrivals), j=0 (departures), platforms=0, maxPlatforms=0

i=0, j=0, platforms=0, maxPlatforms=0

Why: We track arrivals and departures to count overlapping trains.

Step 3: Compare arrival[i]=900 and departure[j]=910; arrival <= departure, so platforms++ and i++

platforms=1, maxPlatforms=1, i=1, j=0

Why: A train arrives before the first train departs, so we need a platform.

Step 4: Compare arrival[i]=940 and departure[j]=910; arrival > departure, so platforms-- and j++

platforms=0, maxPlatforms=1, i=1, j=1

Why: A train departs before next arrival, freeing a platform.

Step 5: Compare arrival[i]=940 and departure[j]=1120; arrival <= departure, so platforms++ and i++

platforms=1, maxPlatforms=1, i=2, j=1

Why: Train arrives before next departure, need platform.

Step 6: Compare arrival[i]=950 and departure[j]=1120; arrival <= departure, so platforms++ and i++

platforms=2, maxPlatforms=2, i=3, j=1

Why: Another train arrives before departure, need another platform.

Step 7: Compare arrival[i]=1100 and departure[j]=1120; arrival <= departure, so platforms++ and i++

platforms=3, maxPlatforms=3, i=4, j=1

Why: Third train arrives before departure, need third platform.

Step 8: Compare arrival[i]=1500 and departure[j]=1120; arrival > departure, so platforms-- and j++

platforms=2, maxPlatforms=3, i=4, j=2

Why: Train departs, freeing a platform.

Step 9: Compare arrival[i]=1500 and departure[j]=1130; arrival > departure, so platforms-- and j++

platforms=1, maxPlatforms=3, i=4, j=3

Why: Another train departs, freeing a platform.

Step 10: Compare arrival[i]=1500 and departure[j]=1200; arrival > departure, so platforms-- and j++

platforms=0, maxPlatforms=3, i=4, j=4

Why: Another train departs, freeing a platform.

Step 11: Compare arrival[i]=1500 and departure[j]=1900; arrival <= departure, so platforms++ and i++

platforms=1, maxPlatforms=3, i=5, j=4

Why: Train arrives before next departure, need platform.

Step 12: Compare arrival[i]=1800 and departure[j]=1900; arrival <= departure, so platforms++ and i++

platforms=2, maxPlatforms=3, i=6, j=4

Why: Another train arrives before departure, need platform.

Step 13: No more arrivals; decrement platforms as trains depart

platforms=1, maxPlatforms=3, j=5
platforms=0, maxPlatforms=3, j=6

Why: Trains depart, freeing platforms.

Result:

Final maxPlatforms = 3
Minimum platforms needed: 3

Annotated Code

DSA Javascript

class TrainPlatform {
  static findMinPlatforms(arrivals, departures) {
    arrivals.sort((a, b) => a - b);
    departures.sort((a, b) => a - b);

    let i = 0, j = 0;
    let platforms = 0, maxPlatforms = 0;

    while (i < arrivals.length && j < departures.length) {
      if (arrivals[i] <= departures[j]) {
        platforms++; // train arrives, need platform
        if (platforms > maxPlatforms) maxPlatforms = platforms; // update max
        i++; // move to next arrival
      } else {
        platforms--; // train departs, free platform
        j++; // move to next departure
      }
    }

    return maxPlatforms;
  }
}

// Driver code
const arrivals = [900, 940, 950, 1100, 1500, 1800];
const departures = [910, 1200, 1120, 1130, 1900, 2000];
const result = TrainPlatform.findMinPlatforms(arrivals, departures);
console.log(result + "\n");

arrivals.sort((a, b) => a - b); departures.sort((a, b) => a - b);

Sort arrival and departure times to process chronologically

if (arrivals[i] <= departures[j]) { platforms++; if (platforms > maxPlatforms) maxPlatforms = platforms; i++; }

Increment platforms when train arrives before next departure, update max platforms

else { platforms--; j++; }

Decrement platforms when train departs before next arrival

Output

3

Complexity Analysis

Time: O(n log n) because sorting arrivals and departures takes O(n log n), and the traversal is O(n)

Space: O(1) because sorting is done in place and only a few variables are used

vs Alternative: Naive approach checks each train against all others for overlap, which is O(n^2), so this method is more efficient

Edge Cases

Empty arrays for arrivals and departures

Returns 0 since no trains need platforms

DSA Javascript

while (i < arrivals.length && j < departures.length)

All trains arrive and depart at the same time

Platforms needed equals number of trains because all overlap

DSA Javascript

if (arrivals[i] <= departures[j]) { platforms++; if (platforms > maxPlatforms) maxPlatforms = platforms; i++; }

Trains with no overlapping times

Platforms needed is 1 because trains do not overlap

DSA Javascript

else { platforms--; j++; }

When to Use This Pattern

When you see problems asking for minimum resources to handle overlapping intervals, use the two-pointer approach on sorted start and end times to find maximum overlap.

Common Mistakes

Mistake: Not sorting arrival and departure arrays before processing
Fix: Sort both arrays to process events in chronological order

Mistake: Using '<' instead of '<=' in comparison, causing off-by-one errors
Fix: Use '<=' to correctly count trains arriving exactly when another departs

Mistake: Incrementing both pointers in the same iteration
Fix: Increment only arrival pointer if arrival <= departure, else increment departure pointer

Summary

Calculates the minimum number of train platforms needed so no train waits by finding maximum overlapping trains.

Use when scheduling resources for intervals that may overlap, like trains or meetings.

Sort arrivals and departures separately and use two pointers to count overlaps efficiently.

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