The “Minimum Platforms” problem is a classic algorithm problem where you need to determine the minimum number of train platforms required to accommodate all trains at a station, given their arrival and departure times.
Problem Statement
Given two arrays:
arr[]
: containing arrival times of trains.dep[]
: containing departure times of trains.
You need to find the minimum number of platforms required so that no train has to wait.
Approach
To solve this problem, we can use a sorting and two-pointer approach:
-
Sort Arrival and Departure Times: First, sort both the arrival and departure times.
-
Use Two Pointers: Use two pointers to track the current train arriving and the current train departing.
-
Count Platforms:
- If a train arrives before or when another departs, increment the platform count.
- If a train departs, decrement the platform count.
-
Track Maximum Platforms: Throughout the process, keep track of the maximum number of platforms needed at any time.
Implementation in C#
Here’s a C# implementation of the above approach:
using System;
public class Program
{
public static void Main()
{
int[] arrival = { 10, 15, 5, 20 }; // Example arrival times
int[] departure = { 20, 30, 10, 25 }; // Example departure times
int result = MinPlatforms(arrival, departure);
Console.WriteLine($"Minimum number of platforms needed: {result}");
}
public static int MinPlatforms(int[] arrival, int[] departure)
{
int n = arrival.Length;
// Sort arrival and departure arrays
Array.Sort(arrival);
Array.Sort(departure);
int platformsNeeded = 0;
int maxPlatforms = 0;
int i = 0; // Pointer for arrival
int j = 0; // Pointer for departure
while (i < n && j < n)
{
// If the next train arrives before or at the time the current train departs
if (arrival[i] <= departure[j])
{
platformsNeeded++;
maxPlatforms = Math.Max(maxPlatforms, platformsNeeded);
i++;
}
// If a train departs, reduce the platform count
else
{
platformsNeeded--;
j++;
}
}
return maxPlatforms;
}
}
Explanation:
-
Input Arrays: The
arrival
anddeparture
arrays represent the times when trains arrive and depart, respectively. -
Sorting:
- We sort both the
arrival
anddeparture
arrays. This allows us to process the times in chronological order.
- We sort both the
-
Two Pointer Technique:
- We initialize two pointers (
i
for arrivals andj
for departures) and a variable (platformsNeeded
) to count the current number of platforms in use. - In a while loop, we check if the next train’s arrival is less than or equal to the next train’s departure:
- If true, we increase the platform count and update the maximum if necessary, then move to the next arrival.
- If false, we decrement the platform count (indicating a train has departed) and move to the next departure.
- We initialize two pointers (
-
Return Result: After the loop ends, the
maxPlatforms
variable contains the minimum number of platforms needed.
Complexity:
- Time Complexity: ( O(n \log n) ) due to the sorting of the arrival and departure times. The two-pointer traversal is ( O(n) ).
- Space Complexity: ( O(1) ) since we are using a constant amount of additional space.
This approach efficiently calculates the minimum number of platforms required for the trains, ensuring that no train waits for a platform.