Minimum Number of Platforms in DSA C#

Mental Model

We want to find the smallest number of train platforms needed so that no train waits. We do this by checking how many trains overlap at the same time.

Analogy: Imagine a parking lot where cars arrive and leave at different times. We want to know the minimum number of parking spots so no car has to wait for a spot.

Time line:  |----Train1----|    |-----Train2-----|  |--Train3--|
Platforms:  [P1] [P2] [P3] ...
We assign trains to platforms so their times don't overlap.

Dry Run Walkthrough

Input: arrivals: [9:00, 9:40, 9:50, 11:00, 15:00, 18:00], departures: [9:10, 12:00, 11:20, 11:30, 19:00, 20:00]

Goal: Find the minimum number of platforms needed so no train waits.

Step 1: Sort arrival and departure times separately.

arrivals: 9:00 -> 9:40 -> 9:50 -> 11:00 -> 15:00 -> 18:00
departures: 9:10 -> 11:20 -> 11:30 -> 12:00 -> 19:00 -> 20:00

Why: Sorting helps us check trains in chronological order to count overlaps.

Step 2: Compare first arrival (9:00) with first departure (9:10). Arrival ≤ departure, so platforms needed = 1.

Platforms needed: 1
arrivals pointer at 9:40, departures pointer at 9:10

Why: First train arrives before the first departs, so we need a platform.

Step 3: Next arrival (9:40) > first departure (9:10), so one train left, reduce platforms to 0, then add new train, platforms = 1.

Platforms needed: 1
arrivals pointer at 9:50, departures pointer at 11:20

Why: Train at 9:00 left before 9:40 arrival, so platform freed.

Step 4: Next arrival (9:50) ≤ next departure (11:20), increase platforms to 2.

Platforms needed: 2
arrivals pointer at 11:00, departures pointer at 11:20

Why: Two trains overlap between 9:50 and 11:20, so need 2 platforms.

Step 5: Next arrival (11:00) ≤ next departure (11:20), increase platforms to 3.

Platforms needed: 3
arrivals pointer at 15:00, departures pointer at 11:20

Why: Three trains overlap between 11:00 and 11:20, so need 3 platforms.

Step 6: Next departure (11:20) < next arrival (15:00), reduce platforms to 2.

Platforms needed: 2
arrivals pointer at 15:00, departures pointer at 11:30

Why: One train left at 11:20, freeing a platform.

Step 7: Next departure (11:30) < next arrival (15:00), reduce platforms to 1.

Platforms needed: 1
arrivals pointer at 15:00, departures pointer at 12:00

Why: Another train left at 11:30, freeing another platform.

Step 8: Next departure (12:00) < next arrival (15:00), reduce platforms to 0.

Platforms needed: 0
arrivals pointer at 15:00, departures pointer at 19:00

Why: Train left at 12:00, freeing platform.

Step 9: Next arrival (15:00) ≤ next departure (19:00), increase platforms to 1.

Platforms needed: 1
arrivals pointer at 18:00, departures pointer at 19:00

Why: Train arrives at 15:00 before previous train departs, need platform.

Step 10: Next arrival (18:00) ≤ next departure (19:00), increase platforms to 2.

Platforms needed: 2
arrivals pointer at end, departures pointer at 19:00

Why: Two trains overlap between 18:00 and 19:00, need 2 platforms.

Result:

Maximum platforms needed at once: 3

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class MinimumPlatforms
{
    public static int FindMinimumPlatforms(int[] arrivals, int[] departures)
    {
        Array.Sort(arrivals); // sort arrival times
        Array.Sort(departures); // sort departure times

        int platformNeeded = 0, maxPlatforms = 0;
        int i = 0, j = 0;

        while (i < arrivals.Length && j < departures.Length)
        {
            if (arrivals[i] <= departures[j])
            {
                platformNeeded++; // train arrives, need platform
                if (platformNeeded > maxPlatforms)
                    maxPlatforms = platformNeeded; // update max
                i++; // move to next arrival
            }
            else
            {
                platformNeeded--; // train departs, free platform
                j++; // move to next departure
            }
        }

        return maxPlatforms;
    }

    static void Main()
    {
        int[] arrivals = { 900, 940, 950, 1100, 1500, 1800 };
        int[] departures = { 910, 1120, 1130, 1200, 1900, 2000 };

        int result = FindMinimumPlatforms(arrivals, departures);
        Console.WriteLine(result);
    }
}

Array.Sort(arrivals); // sort arrival times

sort arrivals to process trains in order

Array.Sort(departures); // sort departure times

sort departures to process trains in order

if (arrivals[i] <= departures[j])

check if next train arrives before current train departs

platformNeeded++; // train arrives, need platform

increase platform count for overlapping train

if (platformNeeded > maxPlatforms) maxPlatforms = platformNeeded;

update max platforms needed so far

i++; // move to next arrival

advance to next train arrival

else { platformNeeded--; j++; }

train departs, free platform and move to next departure

Output

3

Complexity Analysis

Time: O(n log n) because we sort the arrival and departure arrays, then traverse them once.

Space: O(1) because we use only a few extra variables, sorting is in-place.

vs Alternative: Naive approach checks each train against all others, O(n^2), so sorting and two-pointer method is more efficient.

Edge Cases

No trains (empty arrays)

Returns 0 platforms needed.

DSA C#

while (i < arrivals.Length && j < departures.Length)

All trains arrive and depart at the same time

Platforms needed equals number of trains.

DSA C#

if (arrivals[i] <= departures[j])

Trains arrive after previous trains depart (no overlap)

Platforms needed is 1.

DSA C#

else { platformNeeded--; j++; }

When to Use This Pattern

When you see problems asking for minimum resources to handle overlapping intervals, use sorting and two-pointer technique to count overlaps efficiently.

Common Mistakes

Mistake: Not sorting arrival and departure times before processing.
Fix: Always sort both arrays to process events in chronological order.

Mistake: Using arrival < departure instead of arrival <= departure, missing edge overlaps.
Fix: Use <= to correctly count trains arriving exactly when another departs.

Summary

Finds the minimum number of platforms needed so no train waits by counting overlapping train times.

Use when scheduling resources for intervals that may overlap in time.

Sort arrivals and departures separately, then use two pointers to count overlaps and track maximum platforms needed.

Practice

1. What does the "Minimum Number of Platforms" problem ask you to find given train arrival and departure times?

easy

A. The total time trains spend at the station

B. The least number of platforms needed so no train waits

C. The maximum speed of any train

D. The total number of trains arriving in a day

Solution

1. Step 1: Understand the problem context

   The problem wants to find how many platforms are needed so that no train has to wait for another to leave.

2. Step 2: Identify the key output

   The output is the minimum number of platforms required to handle all trains without delay.

3. Final Answer:

   The least number of platforms needed so no train waits -> Option B

4. Quick Check:

   Minimum platforms = no waiting trains [OK]

Hint: Count overlapping trains to find minimum platforms needed [OK]

Common Mistakes:

• Confusing total trains with platforms needed
• Ignoring overlapping arrival and departure times
• Thinking about train speed or duration instead

2. Which of the following C# code snippets correctly declares arrays for arrival and departure times for the Minimum Number of Platforms problem?

easy

A. int arrival = [900, 940, 950]; int departure = [910, 1200, 1120];

B. int arrival[] = (900, 940, 950); int departure[] = (910, 1200, 1120);

C. int[] arrival = {900, 940, 950}; int[] departure = {910, 1200, 1120};

D. int[] arrival = (900, 940, 950); int[] departure = (910, 1200, 1120);

Solution

1. Step 1: Recall C# array declaration syntax

   In C#, arrays are declared with type[], and values inside curly braces {}.

2. Step 2: Check each option for correct syntax

   int[] arrival = {900, 940, 950}; int[] departure = {910, 1200, 1120}; uses int[] and curly braces {}, which is correct. Others use parentheses or wrong syntax.

3. Final Answer:

   int[] arrival = {900, 940, 950}; int[] departure = {910, 1200, 1120}; -> Option C

4. Quick Check:

   C# arrays use type[] and {} [OK]

Hint: Use int[] and curly braces {} for arrays in C# [OK]

Common Mistakes:

• Using parentheses () instead of curly braces {}
• Declaring arrays without [] after type
• Using square brackets [] for initialization

3. What is the output of the following C# code snippet that calculates minimum platforms?

int[] arrival = {900, 940, 950, 1100, 1500, 1800};
int[] departure = {910, 1200, 1120, 1130, 1900, 2000};

int platforms = CalculateMinPlatforms(arrival, departure);
Console.WriteLine(platforms);

// Assume CalculateMinPlatforms correctly implements the algorithm.

medium

A. 5

B. 4

C. 2

D. 3

Solution

1. Step 1: Sort arrival and departure times

   Arrival: 900, 940, 950, 1100, 1500, 1800 Departure: 910, 1120, 1130, 1200, 1900, 2000

2. Step 2: Count overlapping trains to find max platforms

   At 950, trains at 900, 940, 950 overlap (3 trains). Later overlaps are fewer.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Max overlap = 3 platforms [OK]

Hint: Find max overlapping intervals for minimum platforms [OK]

Common Mistakes:

• Not sorting times before counting overlaps
• Counting total trains instead of overlaps
• Mixing arrival and departure arrays

4. Identify the error in this C# code snippet for calculating minimum platforms:

int[] arrival = {900, 940, 950};
int[] departure = {910, 1200, 1120};

Array.Sort(arrival);
Array.Sort(departure);

int i = 0, j = 0, platforms = 0, maxPlatforms = 0;
while (i < arrival.Length && j < departure.Length) {
    if (arrival[i] <= departure[j]) {
        platforms++;
        i++;
    } else {
        platforms--;
        j++;
    }
    maxPlatforms = Math.Max(maxPlatforms, platforms);
}
Console.WriteLine(maxPlatforms);

medium

A. The comparison should be 'arrival[i] < departure[j]' instead of '<='

B. The loop condition should be 'i < arrival.Length || j < departure.Length'

C. The arrays should not be sorted before processing

D. The platforms variable should not be incremented

Solution

1. Step 1: Analyze the comparison operator in the loop

   Using '<=' causes counting a train as arriving exactly when another departs, increasing platforms unnecessarily.

2. Step 2: Correct comparison to '<' to avoid overlap at exact departure time

   Changing to '<' means a train arriving at the same time another departs does not increase platform count.

3. Final Answer:

   The comparison should be 'arrival[i] < departure[j]' instead of '<=' -> Option A

4. Quick Check:

   Use '<' to avoid counting simultaneous arrival and departure as overlap [OK]

Hint: Use '<' not '<=' when comparing arrival and departure [OK]

Common Mistakes:

• Using '<=' causes overcounting platforms
• Not sorting arrays before processing
• Incorrect loop condition causing missed trains

5. Given arrival times [900, 940, 950, 1100, 1500, 1800] and departure times [910, 1200, 1120, 1130, 1900, 2000], how would you modify the algorithm to also return the time intervals when the maximum number of platforms are needed?

hard

A. Track intervals when platform count equals max during iteration and store them

B. Return only the maximum platform count without intervals

C. Sort only arrival times and ignore departure times

D. Count total trains without checking overlaps

Solution

1. Step 1: Modify algorithm to track platform count changes

   While iterating, record start time when platforms reach max and end time when count drops.

2. Step 2: Store intervals where platform count equals maximum

   Keep a list of intervals with max platforms to return after processing all times.

3. Final Answer:

   Track intervals when platform count equals max during iteration and store them -> Option A

4. Quick Check:

   Record max platform intervals during count updates [OK]

Hint: Save start/end times when platform count hits max [OK]

Common Mistakes:

• Ignoring time intervals, returning only counts
• Not updating intervals when platform count changes
• Sorting only one array causing wrong intervals