General

No Comments

Minimum Number of Platforms Required for a Railway Station

This “Minimum Number of Platforms Required for a Railway Station” is one of the most frequently asked DSA questions. I failed to crack two of the interviews due to this question.

Problem Statement

Given the arrival and departure times of trains at a railway station, determine the minimum number of platforms required so that no train has to wait away from the railway station. Assume that the trains arrive and depart on the same day, also 900 means 9:00, 2000 means 20:00.

Examples

  • Input:
    • Arrival times: [900, 940, 950, 1100, 1500, 1800]
    • Departure times: [910, 1200, 1120, 1130, 1900, 2000]
  • Output: 3

  • Input:
    • Arrival times: [200, 210, 300, 320, 350, 500]
    • Departure times: [230, 340, 320, 430, 400, 520]
  • Output: 2

Approach

To solve this problem, we can use a two-pointer technique with the help of sorting. The key idea is to consider each event (arrival or departure) in a sorted manner and keep track of the number of platforms needed at any given time.

Step-by-Step Solution

  1. Sort the Arrival and Departure Times:
    • Sort both the arrival and departure arrays.
  2. Initialize Pointers and Variables:
    • Use two pointers to traverse the arrival and departure arrays.
    • Initialize variables to keep track of the current number of platforms needed and the maximum platforms needed.
  3. Traverse the Events:
    • Use a while loop to iterate through both arrays:
      • If the next event in the sorted order is an arrival, increase the count of platforms needed.
      • If the next event is a departure, decrease the count of platforms needed.
      • Update the maximum number of platforms needed accordingly.

Implementation in JavaScript

Here’s how you can implement the Minimum Number of Platforms Required for a Railway Station in JavaScript:

function findPlatform(arrivals, departures) {
  let n = arrivals.length;
  arrivals.sort((a, b) => a - b);
  departures.sort((a, b) => a - b);

  let platform_needed = 1, max_platforms = 1;
  let i = 1, j = 0;

  while (i < n && j < n) {
    if (arrivals[i] <= departures[j]) {
      platform_needed++;
      i++;
      if (platform_needed > max_platforms) {
        max_platforms = platform_needed;
      }
    } else {
      platform_needed--;
      j++;
    }
  }

  return max_platforms;
}

// Test cases
const arrivalTimes1 = [900, 940, 950, 1100, 1500, 1800];
const departureTimes1 = [910, 1200, 1120, 1130, 1900, 2000];
console.log(findPlatform(arrivalTimes1, departureTimes1)); // Output: 3

const arrivalTimes2 = [200, 210, 300, 320, 350, 500];
const departureTimes2 = [230, 340, 320, 430, 400, 520];
console.log(findPlatform(arrivalTimes2, departureTimes2)); // Output: 2

Time and Space Complexity

  • Time Complexity: O(n log n), where n is the number of trains. This complexity arises from sorting the arrival and departure arrays.
  • Space Complexity: O(1), as we are using a fixed amount of extra space.

Close Menu