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.