Minimum Number of Platforms in DSA Typescript

Mental Model

We want to find the smallest number of train platforms needed so that 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 depends on overlapping times.

Dry Run Walkthrough

Input: Train arrival times: [9:00, 9:40, 9:50, 11:00, 15:00, 18:00], departure times: [9:10, 12:00, 11:20, 11:30, 19:00, 20:00]

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

Step 1: Sort arrival and departure times separately

Arrivals: 9:00 -> 9:40 -> 9:50 -> 11:00 -> 15:00 -> 18:00
Departures: 9:10 -> 11:20 -> 11:30 -> 12:00 -> 19:00 -> 20:00

Why: Sorting helps us compare arrival and departure times in order.

Step 2: Initialize pointers i=0 (arrival), j=0 (departure), platforms=0, maxPlatforms=0

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

Why: We track how many trains are currently at the station.

Step 3: Compare arrival[i] and departure[j]: 9:00 < 9:10, increment platforms to 1, i=1

Platforms=1 (train at 9:00 arrived), maxPlatforms=1

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

Step 4: Compare arrival[i] and departure[j]: 9:40 > 9:10, decrement platforms to 0, j=1

Platforms=0 (train departed at 9:10), maxPlatforms=1

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

Step 5: Compare arrival[i] and departure[j]: 9:40 < 11:20, increment platforms to 1, i=2

Platforms=1 (train arrived at 9:40), maxPlatforms=1

Why: A train arrives before next departure, need platform.

Step 6: Compare arrival[i] and departure[j]: 9:50 < 11:20, increment platforms to 2, i=3

Platforms=2 (trains at 9:40 and 9:50), maxPlatforms=2

Why: Two trains overlap, need two platforms.

Step 7: Compare arrival[i] and departure[j]: 11:00 < 11:20, increment platforms to 3, i=4

Platforms=3 (trains at 9:40, 9:50, 11:00), maxPlatforms=3

Why: Three trains overlap, need three platforms.

Step 8: Compare arrival[i] and departure[j]: 15:00 > 11:20, decrement platforms to 2, j=2

Platforms=2 (one train departed at 11:20), maxPlatforms=3

Why: One train left, freeing a platform.

Step 9: Compare arrival[i] and departure[j]: 15:00 > 11:30, decrement platforms to 1, j=3

Platforms=1 (another train departed at 11:30), maxPlatforms=3

Why: Another train left, freeing a platform.

Step 10: Compare arrival[i] and departure[j]: 15:00 > 12:00, decrement platforms to 0, j=4

Platforms=0 (train departed at 12:00), maxPlatforms=3

Why: Another train left, freeing a platform.

Step 11: Compare arrival[i] and departure[j]: 15:00 < 19:00, increment platforms to 1, i=5

Platforms=1 (train arrived at 15:00), maxPlatforms=3

Why: New train arrived, need platform.

Step 12: Compare arrival[i] and departure[j]: 18:00 < 19:00, increment platforms to 2, i=6

Platforms=2 (trains at 15:00 and 18:00), maxPlatforms=3

Why: Two trains overlap, need two platforms.

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

Platforms=1 after departure at 19:00, then 0 after departure at 20:00, maxPlatforms=3

Why: Trains leave, freeing platforms.

Result:

Final maxPlatforms = 3
Minimum platforms needed: 3

Annotated Code

DSA Typescript

class TrainScheduler {
  static findMinPlatforms(arrivals: number[], departures: number[]): number {
    arrivals.sort((a, b) => a - b);
    departures.sort((a, b) => a - b);

    let platformNeeded = 0;
    let maxPlatforms = 0;
    let i = 0; // arrival pointer
    let j = 0; // departure pointer

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

    return maxPlatforms;
  }
}

// Driver code with example input
const arrivals = [900, 940, 950, 1100, 1500, 1800];
const departures = [910, 1200, 1120, 1130, 1900, 2000];
const minPlatforms = TrainScheduler.findMinPlatforms(arrivals, departures);
console.log(`Minimum platforms needed: ${minPlatforms}`);

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

Sort arrival and departure times to compare in order

if (arrivals[i] < departures[j]) { platformNeeded++; maxPlatforms = Math.max(maxPlatforms, platformNeeded); i++; }

If next train arrives before a train departs, increase platform count

else { platformNeeded--; j++; }

If train departs before next arrival, decrease platform count

Output

Minimum platforms needed: 3

Complexity Analysis

Time: O(n log n) because we sort the arrival and departure arrays of length 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 leading to O(n^2) time, this approach is more efficient.

Edge Cases

No trains (empty arrays)

Returns 0 platforms needed

DSA Typescript

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

All trains arrive and depart at the same time

Platforms needed equals number of trains

DSA Typescript

maxPlatforms = Math.max(maxPlatforms, platformNeeded)

Trains arrive after all others depart (no overlap)

Platforms needed is 1

DSA Typescript

if (arrivals[i] < departures[j])

When to Use This Pattern

When you see overlapping time intervals and need to find the maximum overlap, use the two-pointer approach on sorted start and end times to find the minimum resources needed.

Common Mistakes

Mistake: Not sorting arrival and departure times before processing
Fix: Sort both arrays to ensure correct order of events

Mistake: Using <= instead of < in comparison, causing incorrect platform count
Fix: Use strictly less than (<) to count arrivals before departures

Summary

Calculates the minimum number of platforms needed so no train waits by counting overlapping train times.

Use when scheduling resources that must handle overlapping intervals without delay.

Sort arrival and departure times separately and use two pointers to track overlaps efficiently.