Minimum Platforms in c#

Programming C#
1

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:

  1. Sort Arrival and Departure Times: First, sort both the arrival and departure times.

  2. Use Two Pointers: Use two pointers to track the current train arriving and the current train departing.

  3. Count Platforms:

    • If a train arrives before or when another departs, increment the platform count.
    • If a train departs, decrement the platform count.

  4. 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:

  1. Input Arrays: The arrival and departure arrays represent the times when trains arrive and depart, respectively.

  2. Sorting:

    • We sort both the arrival and departure arrays. This allows us to process the times in chronological order.

  3. Two Pointer Technique:

    • We initialize two pointers (i for arrivals and j 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.

  4. 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.