Minimum Number of Platforms in DSA C - Time & Space Complexity

Time Complexity: Minimum Number of Platforms

O(n log n)

Understanding Time Complexity

We want to find out how the time needed to find the minimum number of train platforms changes as the number of trains increases.

Specifically, we ask: How does the running time grow when we have more arrival and departure times?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void findPlatforms(int arr[], int dep[], int n) {
    sort(arr, arr + n);
    sort(dep, dep + n);
    int i = 0, j = 0, platforms = 0, maxPlatforms = 0;
    while (i < n && j < n) {
        if (arr[i] <= dep[j]) {
            platforms++;
            i++;
            if (platforms > maxPlatforms) maxPlatforms = platforms;
        } else {
            platforms--;
            j++;
        }
    }
}
    

This code finds the minimum number of platforms needed so that no train waits, by sorting arrival and departure times and then scanning them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the arrival and departure arrays, and then scanning both arrays once.
• How many times: Sorting takes multiple comparisons (depends on n), scanning uses a single loop that runs at most 2n times.

How Execution Grows With Input

Sorting takes more time as the number of trains grows, and scanning grows linearly with the number of trains.

Input Size (n)	Approx. Operations
10	About 10 log 10 + 20 = 50 operations
100	About 100 log 100 + 200 = 900 operations
1000	About 1000 log 1000 + 2000 = 13000 operations

Pattern observation: The sorting dominates and grows faster than scanning, roughly n log n growth.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a bit faster than the number of trains, mainly because sorting takes more time as trains increase.

Common Mistake

[X] Wrong: "The scanning loop alone makes this O(n) time."

[OK] Correct: Sorting the arrays first takes more time than scanning, so the total time is not just linear but includes sorting time.

Interview Connect

Understanding this time complexity helps you explain how sorting and scanning work together efficiently to solve real scheduling problems.

Self-Check

"What if the arrival and departure arrays were already sorted? How would the time complexity change?"