Minimum Number of Platforms in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the minimum number of platforms needed?

Given arrival and departure times of trains, what is the minimum number of platforms required so that no train waits?

DSA Typescript

function findPlatform(arr: number[], dep: number[], n: number): number {
  arr.sort((a, b) => a - b);
  dep.sort((a, b) => a - b);
  let platform_needed = 1, result = 1;
  let i = 1, j = 0;
  while (i < n && j < n) {
    if (arr[i] <= dep[j]) {
      platform_needed++;
      i++;
      if (platform_needed > result) result = platform_needed;
    } else {
      platform_needed--;
      j++;
    }
  }
  return result;
}

const arr = [900, 940, 950, 1100, 1500, 1800];
const dep = [910, 1200, 1120, 1130, 1900, 2000];
console.log(findPlatform(arr, dep, arr.length));

A 4

B 3

C 2

D 5

💡 Hint

Sort arrival and departure times separately and compare them to count overlaps.

The function sorts arrival and departure times. It uses two pointers to track trains arriving and leaving. When a train arrives before the earliest departure, we need an extra platform. When a train departs, a platform is freed. The maximum platforms needed at any time is 3.

❓ Predict Output

intermediate

Output of platform calculation with overlapping trains

What is the output of the following code that calculates minimum platforms?

DSA Typescript

const arrivals = [1000, 1010, 1025, 1030];
const departures = [1015, 1020, 1035, 1040];
function minPlatforms(arr: number[], dep: number[]): number {
  arr.sort((a, b) => a - b);
  dep.sort((a, b) => a - b);
  let platforms = 1, maxPlatforms = 1;
  let i = 1, j = 0;
  while (i < arr.length && j < dep.length) {
    if (arr[i] <= dep[j]) {
      platforms++;
      i++;
      if (platforms > maxPlatforms) maxPlatforms = platforms;
    } else {
      platforms--;
      j++;
    }
  }
  return maxPlatforms;
}
console.log(minPlatforms(arrivals, departures));

A 3

B 4

C 2

D 1

💡 Hint

Count how many trains overlap at the same time.

The trains overlap such that at one point 2 trains are at the station simultaneously, so 2 platforms are needed.

🧠 Conceptual

advanced

Why do we sort arrival and departure times separately?

In the minimum number of platforms problem, why is it important to sort arrival and departure times separately before processing?

A To process events in chronological order and correctly count overlapping trains

B To group all arrivals before departures for easier counting

C To ensure trains are processed in the order they appear in input

D To reduce the time complexity to O(n) without sorting

💡 Hint

Think about how to track when trains overlap in time.

Sorting arrivals and departures separately allows us to process all events in chronological order, comparing the next arrival and departure to count how many trains are at the station simultaneously.

🔧 Debug

advanced

Identify the error in this platform calculation code

What error will this code produce when calculating minimum platforms?

DSA Typescript

function findMinPlatforms(arr: number[], dep: number[]): number {
  arr.sort();
  dep.sort();
  let platforms = 1, maxPlatforms = 1;
  let i = 1, j = 0;
  while (i < arr.length && j < dep.length) {
    if (arr[i] < dep[j]) {
      platforms++;
      i++;
      if (platforms > maxPlatforms) maxPlatforms = platforms;
    } else {
      platforms--;
      j++;
    }
  }
  return maxPlatforms;
}

const arrivals = [900, 940, 950, 1100];
const departures = [910, 1200, 1120, 1130];
console.log(findMinPlatforms(arrivals, departures));

A The sort() method sorts numbers as strings causing incorrect order

B The comparison operator should be <= instead of <

C The loop condition should be i <= arr.length

D The initial platforms count should be 0 instead of 1

💡 Hint

Check how JavaScript's sort() works on numbers without a compare function.

Using sort() without a compare function sorts numbers as strings, so 950 comes before 940, causing wrong platform count.

🚀 Application

expert

Calculate platforms needed for large input efficiently

You have 1 million trains with arrival and departure times. Which approach is best to find the minimum number of platforms needed efficiently?

A Check each train against all others to count overlaps in O(n^2) time

B Sort trains by arrival time only and count platforms by incrementing for each train

C Use a hash map to count trains at each minute and find max count in O(n) time

D Sort arrivals and departures separately and use two pointers to count overlaps in O(n log n) time

💡 Hint

Consider time complexity and memory usage for large inputs.

Sorting arrivals and departures separately and using two pointers is efficient (O(n log n)) and scalable for large inputs. Checking all pairs is too slow. Hash map counting each minute is memory heavy. Sorting only arrivals misses departure order.

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