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 are at the station 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 waits for a spot.

Time line:  
Arrivals:  |--A1--|    |--A2--|    |--A3--|
Departures:    |--D1--|    |--D2--|    |--D3--|
Platforms needed depends on how many intervals overlap.

Dry Run Walkthrough

Input: arrivals: [900, 940, 950, 1100, 1500, 1800], departures: [910, 1200, 1120, 1130, 1900, 2000]

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

Step 1: Sort arrivals and departures separately

arrivals: [900, 940, 950, 1100, 1500, 1800]
departures: [910, 1120, 1130, 1200, 1900, 2000]

Why: Sorting helps us process events in chronological order.

Step 2: Initialize pointers i=0 (arrivals), j=0 (departures), platforms=0, max_platforms=0

i=0, j=0, platforms=0, max_platforms=0

Why: We start checking from the earliest arrival and departure.

Step 3: Compare arrival[i]=900 and departure[j]=910; since 900 < 910, increment platforms and i

platforms=1, max_platforms=1, i=1, j=0

Why: A train arrives before the first departure, so we need a platform.

Step 4: Compare arrival[i]=940 and departure[j]=910; since 940 > 910, decrement platforms and increment j

platforms=0, max_platforms=1, i=1, j=1

Why: A train departs before next arrival, freeing a platform.

Step 5: Compare arrival[i]=940 and departure[j]=1120; since 940 < 1120, increment platforms and i

platforms=1, max_platforms=1, i=2, j=1

Why: A train arrives before next departure, need a platform.

Step 6: Compare arrival[i]=950 and departure[j]=1120; since 950 < 1120, increment platforms and i

platforms=2, max_platforms=2, i=3, j=1

Why: Another train arrives before departure, need another platform.

Step 7: Compare arrival[i]=1100 and departure[j]=1120; since 1100 < 1120, increment platforms and i

platforms=3, max_platforms=3, i=4, j=1

Why: Another train arrives before departure, need another platform.

Step 8: Compare arrival[i]=1500 and departure[j]=1120; since 1500 > 1120, decrement platforms and j

platforms=2, max_platforms=3, i=4, j=2

Why: A train departs, freeing a platform.

Step 9: Compare arrival[i]=1500 and departure[j]=1130; since 1500 > 1130, decrement platforms and j

platforms=1, max_platforms=3, i=4, j=3

Why: Another train departs, freeing a platform.

Step 10: Compare arrival[i]=1500 and departure[j]=1200; since 1500 > 1200, decrement platforms and j

platforms=0, max_platforms=3, i=4, j=4

Why: Another train departs, freeing a platform.

Step 11: Compare arrival[i]=1500 and departure[j]=1900; since 1500 < 1900, increment platforms and i

platforms=1, max_platforms=3, i=5, j=4

Why: A train arrives before departure, need a platform.

Step 12: Compare arrival[i]=1800 and departure[j]=1900; since 1800 < 1900, increment platforms and i

platforms=2, max_platforms=3, i=6, j=4

Why: Another train arrives before departure, need another platform.

Step 13: No more arrivals; decrement platforms as departures happen

platforms=1, max_platforms=3, i=6, j=5

Why: Trains depart, freeing platforms.

Step 14: Final departure frees last platform

platforms=0, max_platforms=3, i=6, j=6

Why: All trains have departed.

Result:

Final max_platforms = 3
Platforms needed: 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

int minPlatforms(int arrivals[], int departures[], int n) {
    // Sort arrivals
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arrivals[j] > arrivals[j + 1]) {
                int temp = arrivals[j]; arrivals[j] = arrivals[j + 1]; arrivals[j + 1] = temp;
            }
            if (departures[j] > departures[j + 1]) {
                int temp = departures[j]; departures[j] = departures[j + 1]; departures[j + 1] = temp;
            }
        }
    }

    int i = 0, j = 0;
    int platforms = 0, max_platforms = 0;

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

    return max_platforms;
}

int main() {
    int arrivals[] = {900, 940, 950, 1100, 1500, 1800};
    int departures[] = {910, 1200, 1120, 1130, 1900, 2000};
    int n = sizeof(arrivals) / sizeof(arrivals[0]);

    int result = minPlatforms(arrivals, departures, n);
    printf("Minimum number of platforms needed: %d\n", result);
    return 0;
}

for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arrivals[j] > arrivals[j + 1]) { ... } if (departures[j] > departures[j + 1]) { ... } } }

Sort arrivals and departures arrays to process events in order

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

Traverse arrivals and departures to count platforms needed at each time

Output

Minimum number of platforms needed: 3

Complexity Analysis

Time: O(n^2) because of bubble sort used for sorting arrivals and departures arrays

Space: O(1) because sorting is done in place and only a few variables are used

vs Alternative: Using a more efficient sort like quicksort or mergesort reduces time to O(n log n), improving performance for large inputs

Edge Cases

No trains (empty arrays)

Returns 0 platforms needed

DSA C

while (i < n && j < n) { ... }

All trains arrive and depart at the same time

Platforms needed equals number of trains

DSA C

if (arrivals[i] < departures[j]) { platforms++; ... } else { platforms--; ... }

Trains with overlapping times

Calculates maximum overlap correctly

DSA C

if (arrivals[i] < departures[j]) { platforms++; ... } else { platforms--; ... }

When to Use This Pattern

When you see problems asking for the minimum number of resources needed to handle overlapping intervals, use the two-pointer approach on sorted start and end times to find maximum overlap.

Common Mistakes

Mistake: Not sorting arrivals and departures separately before processing
Fix: Sort both arrays independently to ensure correct chronological order

Mistake: Using <= instead of < in comparison, causing incorrect platform count
Fix: Use strictly less than (<) to count arrivals before departures correctly

Summary

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

Use when you need to find the maximum number of overlapping intervals in scheduling problems.

The key insight is to sort arrival and departure times separately and count how many trains are at the station simultaneously.

Practice

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

easy

A. The earliest train arrival time

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

C. The total number of trains arriving in a day

D. The maximum number of trains arriving at the same time

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of platforms required so that no train has to wait for another to leave.

2. Step 2: Clarify what is being counted

   We count how many trains overlap in time, which determines how many platforms are needed simultaneously.

3. Final Answer:

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

4. Quick Check:

   Minimum platforms = max trains overlapping [OK]

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

Common Mistakes:

• Confusing total trains with platforms needed
• Ignoring overlapping times
• Counting only arrivals or departures

2. Which of the following C code snippets correctly declares arrays for train arrival and departure times for 5 trains?

easy

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

B. int arrival = {900, 940, 950, 1100, 1500}; int departure = {910, 1200, 1120, 1130, 1900};

C. int arrival[5] = (900, 940, 950, 1100, 1500); int departure[5] = (910, 1200, 1120, 1130, 1900);

D. int arrival[] = 900, 940, 950, 1100, 1500; int departure[] = 910, 1200, 1120, 1130, 1900;

Solution

1. Step 1: Check array declaration syntax in C

   Arrays must be declared with size or empty brackets and initialized with curly braces {}.

2. Step 2: Validate each option

   int arrival[5] = {900, 940, 950, 1100, 1500}; int departure[5] = {910, 1200, 1120, 1130, 1900}; uses correct syntax with size and braces. Others use incorrect syntax like parentheses or missing braces.

3. Final Answer:

   int arrival[5] = {900, 940, 950, 1100, 1500}; int departure[5] = {910, 1200, 1120, 1130, 1900}; -> Option A

4. Quick Check:

   Arrays use {} with size or empty brackets [OK]

Hint: Use curly braces {} to initialize arrays in C [OK]

Common Mistakes:

• Using parentheses () instead of braces {}
• Missing array size or empty brackets
• Assigning values without braces

3. Given arrival times {900, 940, 950, 1100, 1500} and departure times {910, 1200, 1120, 1130, 1900}, what is the minimum number of platforms needed? Consider the following code snippet:

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

// Assume arrays are sorted
int i = 1, j = 0, platforms = 1, result = 1;
while (i < n && j < n) {
  if (arrival[i] <= departure[j]) {
    platforms++;
    i++;
    if (platforms > result) result = platforms;
  } else {
    platforms--;
    j++;
  }
}
printf("%d", result);

medium

A. 4

B. 2

C. 1

D. 3

Solution

1. Step 1: Trace the platform count with given times

   Starts platforms=1 (900 arrival), i=1, j=0. 940 <= 910? No, so platforms--, j=1. Then 940 <= 1200: platforms++, i=2. 950 <= 1200: platforms++, i=3. 1100 <= 1200: platforms++, i=4 (max=3). Later departures reduce platforms.

2. Step 2: Find max platforms during iteration

   Maximum platforms reached is 3 (trains 940-1200, 950-1120, 1100-1130 overlap).

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Max overlapping trains = 3 [OK]

Hint: Sort times and count overlaps to find max platforms [OK]

Common Mistakes:

• Not sorting arrival and departure arrays
• Incorrectly incrementing or decrementing platform count
• Confusing <= with < in comparisons

4. Identify the error in the following code snippet for calculating minimum platforms:

int arrival[] = {900, 940, 950, 1100, 1500};
int departure[] = {910, 1200, 1120, 1130, 1900};
int n = 5;
int i = 0, j = 0, platforms = 0, result = 0;
while (i < n && j < n) {
  if (arrival[i] < departure[j]) {
    platforms++;
    i++;
    if (platforms > result) result = platforms;
  } else {
    platforms--;
    j++;
  }
}
printf("%d", result);

medium

A. No error, code is correct

B. Initialization of platforms should start at 1

C. Loop condition should be i <= n && j <= n

D. Comparison should be arrival[i] <= departure[j]

Solution

1. Step 1: Verify initialization and first steps

   platforms=0, i=0, j=0 correct. 900 < 910: platforms=1, i=1, result=1.

2. Step 2: Check logic and trace

   940 < 910? No: platforms=0, j=1. Then 940 < 1200: platforms=1, i=2; 950<1200:2, i=3; 1100<1200:3, i=4 (max=3). Continues correctly. < handles equal times optimally.

3. Final Answer:

   No error, code is correct -> Option A

4. Quick Check:

   Code outputs 3, matching overlaps [OK]

Hint: plat=0, i=0,j=0, if arr[i] < dep[j] correctly minimizes platforms [OK]

Common Mistakes:

• Using arrival[i] <= departure[j] (overcounts on equal times)
• Initializing platforms=1 with i=0 (overcounts first arrival)
• Loop i <= n && j <= n (off-by-one)

5. You have arrival times {900, 940, 950, 1100, 1500, 1800} and departure times {910, 1200, 1120, 1130, 1900, 2000}. How would you modify the algorithm to handle trains arriving and departing at the same time (e.g., arrival[i] == departure[j]) to minimize platforms needed?

hard

A. Ignore trains with equal arrival and departure times

B. Treat arrival[i] == departure[j] as arrival first to allocate platform

C. Treat arrival[i] == departure[j] as departure first to free platform

D. Increase platform count by 2 when times are equal

Solution

1. Step 1: Understand impact of equal arrival and departure times

   If a train departs at the same time another arrives, the platform can be reused without adding a new one.

2. Step 2: Adjust comparison logic

   When arrival[i] == departure[j], count departure first to free platform before arrival increments platform count.

3. Final Answer:

   Treat arrival[i] == departure[j] as departure first to free platform -> Option C

4. Quick Check:

   Departure before arrival frees platform [OK]

Hint: Count departures before arrivals when times are equal [OK]

Common Mistakes:

• Counting arrival before departure causing extra platform
• Ignoring equal times leading to wrong count
• Adding platforms unnecessarily