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.

Practice

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

easy

A. The total time trains spend on the platform

B. The total number of trains arriving in a day

C. The maximum speed of trains on the platform

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

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of platforms required so that no train has to wait for another to leave.

2. Step 2: Clarify what is being counted

   We count overlapping train schedules to find the peak number of trains at the station simultaneously.

3. Final Answer:

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

4. Quick Check:

   Minimum platforms = max trains overlapping [OK]

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

Common Mistakes:

• Confusing total trains with platforms needed
• Ignoring overlapping times
• Counting total arrival or departure times only

2. Which of the following TypeScript 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 sorting numbers in TypeScript

   Default sort() treats elements as strings, so numeric sort needs a compare function.

2. Step 2: Identify correct compare function

   The function (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 ascending sort uses (a, b) => a - b [OK]

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

Common Mistakes:

• Using sort() without compare function for numbers
• Using (a, b) => a + b which is invalid
• Sorting descending when ascending needed

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

medium

A. 2

B. 3

C. 4

D. 5

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 arrive (1 platform), 910 depart (0), 940 arrive (1), 950 arrive (2), 1100 arrive (3), 1120 depart (2), 1130 depart (1), 1200 depart (0), 1500 arrive (1), 1800 arrive (2), 1900 depart (1), 2000 depart (0). Maximum platforms needed is 4.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Max overlapping trains = 4 [OK]

Hint: Track arrivals and departures to find max overlap [OK]

Common Mistakes:

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

4. The following TypeScript code tries to find the minimum number of platforms but has a bug. What is the bug?

function findPlatforms(arrivals: number[], departures: number[]): number {
  arrivals.sort((a, b) => a - b);
  departures.sort((a, b) => a - b);
  let platformNeeded = 1, maxPlatforms = 1;
  let i = 1, j = 0;
  while (i < arrivals.length && j < departures.length) {
    if (arrivals[i] <= departures[j]) {
      platformNeeded++;
      i++;
    } else {
      platformNeeded--;
      j++;
    }
    if (platformNeeded > maxPlatforms) maxPlatforms = platformNeeded;
  }
  return maxPlatforms;
}

medium

A. Start i from 0 instead of 1 to include first arrival

B. Use < instead of <= in comparison to avoid counting overlaps wrongly

C. Initialize platformNeeded to 0 instead of 1

D. Sort arrivals and departures in descending order

Solution

1. Step 1: Analyze loop initialization

   Variable i starts at 1, skipping the first arrival time, which causes missing counting the first train.

2. Step 2: Correct initialization for accurate counting

   Starting i at 0 ensures all arrivals are considered, giving correct platform count.

3. Final Answer:

   Start i from 0 instead of 1 to include first arrival -> Option A

4. Quick Check:

   Include all arrivals by starting i=0 [OK]

Hint: Start pointers at 0 to include all trains [OK]

Common Mistakes:

• Skipping first arrival by starting i at 1
• Changing comparison operator incorrectly
• Initializing platformNeeded wrongly

5. You have trains arriving and departing as follows: Arrivals: [1000, 1010, 1025, 1030, 1040] Departures: [1015, 1020, 1035, 1045, 1050] If you want to minimize the number of platforms by rescheduling trains without changing their arrival order, which train's departure time should you delay to reduce platform count?

hard

A. Delay the departure of train arriving at 1010

B. Delay the departure of train arriving at 1000

C. Delay the departure of train arriving at 1040

D. Delay the departure of train arriving at 1025

Solution

1. Step 1: Identify overlapping trains causing max platforms

   Trains at 1010 and 1025 overlap because 1010 departs at 1020 and 1025 arrives before that.

2. Step 2: Delay departure of train at 1010 to after 1025 departs

   Delaying 1010's departure reduces overlap with 1025, lowering platform need.

3. Final Answer:

   Delay the departure of train arriving at 1010 -> Option A

4. Quick Check:

   Delay overlapping train's departure to reduce platforms [OK]

Hint: Delay departure of earliest overlapping train to reduce platforms [OK]

Common Mistakes:

• Delaying wrong train's departure
• Changing arrival order which is fixed
• Ignoring overlap timing details