Minimum Number of Platforms in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the minimum number of platforms needed?

Given arrival and departure times of trains, what is the minimum number of platforms required so that no train waits?

DSA C

int findPlatform(int arr[], int dep[], int n) {
    int platform_needed = 1, result = 1;
    int i = 1, j = 0;
    while (i < n && j < n) {
        if (arr[i] <= dep[j]) {
            platform_needed++;
            i++;
            if (platform_needed > result)
                result = platform_needed;
        } else {
            platform_needed--;
            j++;
        }
    }
    return result;
}

// Example usage:
// arr = {900, 940, 950, 1100, 1500, 1800}
// dep = {910, 1200, 1120, 1130, 1900, 2000}
// n = 6
// printf("%d", findPlatform(arr, dep, n));

A 3

B 4

C 2

D 5

💡 Hint

Sort arrival and departure times and compare them to find overlaps.

The function counts how many trains overlap at any time. The maximum overlap is the minimum number of platforms needed.

❓ Predict Output

intermediate

Output of platform calculation with unsorted input arrays

What will be the output of the function if arrival and departure arrays are not sorted?

DSA C

int findPlatform(int arr[], int dep[], int n) {
    int platform_needed = 1, result = 1;
    int i = 1, j = 0;
    while (i < n && j < n) {
        if (arr[i] <= dep[j]) {
            platform_needed++;
            i++;
            if (platform_needed > result)
                result = platform_needed;
        } else {
            platform_needed--;
            j++;
        }
    }
    return result;
}

// Example usage:
// arr = {950, 900, 1100, 940, 1500, 1800}
// dep = {1120, 910, 1130, 1200, 1900, 2000}
// n = 6
// printf("%d", findPlatform(arr, dep, n));

A 3

B 2

C 1

D 4

💡 Hint

The function assumes sorted arrays; unsorted input breaks logic.

Without sorting, the function compares times incorrectly, leading to wrong platform count.

🧠 Conceptual

advanced

Why sorting arrival and departure times is essential?

Why must arrival and departure arrays be sorted before calculating minimum platforms?

A To ensure trains are processed in chronological order to detect overlaps correctly.

B To reduce the time complexity from O(n^2) to O(n log n).

C To group trains by their platform number.

D To avoid using extra memory for storing platforms.

💡 Hint

Think about how overlapping intervals are detected.

Sorting allows comparing arrival and departure times in order, so overlaps are detected accurately.

🔧 Debug

advanced

Identify the bug in this platform calculation code

What is the bug in this code snippet for finding minimum platforms?

DSA C

int findPlatform(int arr[], int dep[], int n) {
    int platform_needed = 1, result = 1;
    int i = 0, j = 0;
    while (i < n && j < n) {
        if (arr[i] < dep[j]) {
            platform_needed++;
            i++;
            if (platform_needed > result)
                result = platform_needed;
        } else {
            platform_needed--;
            j++;
        }
    }
    return result;
}

A The initial value of i should be 1, not 0.

B The function should return platform_needed instead of result.

C The platform_needed should never be decremented.

D The comparison should be arr[i] <= dep[j], not arr[i] < dep[j].

💡 Hint

Consider trains arriving exactly when another departs.

Using < misses the case when arrival equals departure, causing incorrect platform count.

🚀 Application

expert

Calculate platforms for large input with overlapping trains

Given these arrival and departure times, what is the minimum number of platforms needed? arr = {100, 140, 150, 200, 215, 400} dep = {110, 300, 220, 230, 315, 600} n = 6

A 3

B 4

C 5

D 6

💡 Hint

Sort arrays and count maximum overlaps step-by-step.

Maximum overlap occurs between trains arriving at 140, 150, 200, and 215, requiring 4 platforms.

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