Minimum Platforms

In this article, we will solve the problem of determining the minimum number of platforms required at a railway station.

Problem Statement: We are given two arrays, arr[] and dep[], which represent the arrival and departure times of n trains respectively. Our task is to find the minimum number of platforms required at the station so that no train has to wait.

Example:

Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}, dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}, n = 6

Output: 3

Input: arr[] = {10:00, 11:00, 12:00}, dep[] = {10:30, 11:30, 12:30}, n = 3

Output: 1

Solution:

To solve this problem, we will follow these steps:

Steps to Solve:

1.    Sort Arrival and Departure Times:

o   Sort both the arrival and departure arrays.

2.    Initialize Counters:

o   Use two pointers to traverse the sorted arrays.

o   We will then initialize counters for the current number of platforms needed and the maximum number of platforms required.

3.    Traverse Timings:

o   Compare the current arrival time with the current departure time.

o   If a train arrives before the next train departs, increment the platform counter and move to the next arrival time.

o   If a train departs before the next train arrives, decrement the platform counter and move to the next departure time.

o   Update the maximum number of platforms needed during the traversal.

Time Complexity: O(N log N)

Space Complexity: O(1)