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.