Meeting Rooms Problem Minimum Rooms Required in DSA C - Time & Space Complexity

Time Complexity: Meeting Rooms Problem Minimum Rooms Required

O(n log n)

Understanding Time Complexity

We want to find out how the time needed grows when we find the minimum number of meeting rooms required for given meeting times.

How does the program's work increase as the number of meetings grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int minMeetingRooms(int* startTimes, int* endTimes, int n) {
    qsort(startTimes, n, sizeof(int), compare);
    qsort(endTimes, n, sizeof(int), compare);

    int rooms = 0, endPtr = 0;
    for (int i = 0; i < n; i++) {
        if (startTimes[i] < endTimes[endPtr]) {
            rooms++;
        } else {
            endPtr++;
        }
    }
    return rooms;
}

int main() {
    int starts[] = {0, 5, 15};
    int ends[] = {30, 10, 20};
    int n = 3;
    printf("Minimum rooms required: %d\n", minMeetingRooms(starts, ends, n));
    return 0;
}
    

This code finds the minimum number of meeting rooms needed by sorting start and end times and then comparing them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the start and end time arrays.
• How many times: Each sorting runs once on n elements, and then a single loop runs n times to count rooms.

How Execution Grows With Input

Sorting takes more time as the number of meetings grows, and the loop grows linearly with the number of meetings.

Input Size (n)	Approx. Operations
10	About 10 * log 10 + 10 = 43 operations
100	About 100 * log 100 + 100 = 700 operations
1000	About 1000 * log 1000 + 1000 = 10,000 operations

Pattern observation: The work grows a bit faster than the number of meetings because of sorting, but the counting loop grows directly with the number of meetings.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a little faster than the number of meetings because sorting takes more time as the list grows.

Common Mistake

[X] Wrong: "The time complexity is just O(n) because we only loop once through the meetings."

[OK] Correct: Sorting the start and end times takes more time than just looping, so the sorting step dominates the total time.

Interview Connect

Understanding how sorting and simple loops combine to affect time helps you explain your solution clearly and shows you know how to analyze real problems.

Self-Check

"What if the meeting times were already sorted? How would the time complexity change?"