Meeting Rooms Problem Minimum Rooms Required in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum meeting rooms required for given intervals

What is the output of the following C code that calculates the minimum number of meeting rooms required for the given intervals?

DSA C

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

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

int minMeetingRooms(int** intervals, int intervalsSize, int* intervalsColSize) {
    int* start = (int*)malloc(intervalsSize * sizeof(int));
    int* end = (int*)malloc(intervalsSize * sizeof(int));
    for (int i = 0; i < intervalsSize; i++) {
        start[i] = intervals[i][0];
        end[i] = intervals[i][1];
    }
    qsort(start, intervalsSize, sizeof(int), compare);
    qsort(end, intervalsSize, sizeof(int), compare);

    int rooms = 0, endPtr = 0;
    for (int i = 0; i < intervalsSize; i++) {
        if (start[i] < end[endPtr]) {
            rooms++;
        } else {
            endPtr++;
        }
    }
    free(start);
    free(end);
    return rooms;
}

int main() {
    int interval1[] = {0, 30};
    int interval2[] = {5, 10};
    int interval3[] = {15, 20};
    int* intervals[] = {interval1, interval2, interval3};
    int intervalsColSize[] = {2, 2, 2};
    int result = minMeetingRooms(intervals, 3, intervalsColSize);
    printf("%d\n", result);
    return 0;
}

A 2

B 3

C 1

D 0

💡 Hint

Think about how many meetings overlap at the same time.

The code sorts start and end times separately. It then iterates over start times and compares with the earliest end time. If a meeting starts before the earliest meeting ends, we need a new room. Otherwise, we reuse a room. For the given intervals, the maximum overlap is 2.

❓ Predict Output

intermediate

Minimum rooms required for non-overlapping intervals

What is the output of the following code when intervals do not overlap?

DSA C

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

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

int minMeetingRooms(int** intervals, int intervalsSize, int* intervalsColSize) {
    int* start = (int*)malloc(intervalsSize * sizeof(int));
    int* end = (int*)malloc(intervalsSize * sizeof(int));
    for (int i = 0; i < intervalsSize; i++) {
        start[i] = intervals[i][0];
        end[i] = intervals[i][1];
    }
    qsort(start, intervalsSize, sizeof(int), compare);
    qsort(end, intervalsSize, sizeof(int), compare);

    int rooms = 0, endPtr = 0;
    for (int i = 0; i < intervalsSize; i++) {
        if (start[i] < end[endPtr]) {
            rooms++;
        } else {
            endPtr++;
        }
    }
    free(start);
    free(end);
    return rooms;
}

int main() {
    int interval1[] = {1, 2};
    int interval2[] = {3, 4};
    int interval3[] = {5, 6};
    int* intervals[] = {interval1, interval2, interval3};
    int intervalsColSize[] = {2, 2, 2};
    int result = minMeetingRooms(intervals, 3, intervalsColSize);
    printf("%d\n", result);
    return 0;
}

A 3

B 0

C 1

D 2

💡 Hint

No meetings overlap, so only one room is needed.

Since none of the meetings overlap, the code will only need one room to accommodate all meetings sequentially.

🔧 Debug

advanced

Identify the error in the meeting rooms code

What error will this code produce when run, and why?

DSA C

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

int minMeetingRooms(int** intervals, int intervalsSize) {
    int* start = (int*)malloc(intervalsSize * sizeof(int));
    int* end = (int*)malloc(intervalsSize * sizeof(int));
    for (int i = 0; i < intervalsSize; i++) {
        start[i] = intervals[i][0];
        end[i] = intervals[i][1];
    }
    qsort(start, intervalsSize, sizeof(int), (int(*)(const void*, const void*))strcmp);
    qsort(end, intervalsSize, sizeof(int), (int(*)(const void*, const void*))strcmp);

    int rooms = 0, endPtr = 0;
    for (int i = 0; i < intervalsSize; i++) {
        if (start[i] < end[endPtr]) {
            rooms++;
        } else {
            endPtr++;
        }
    }
    free(start);
    free(end);
    return rooms;
}

int main() {
    int interval1[] = {0, 30};
    int interval2[] = {5, 10};
    int interval3[] = {15, 20};
    int* intervals[] = {interval1, interval2, interval3};
    int result = minMeetingRooms(intervals, 3);
    printf("%d\n", result);
    return 0;
}

A Runtime error due to invalid comparison function in qsort

B Compilation error due to missing intervalsColSize parameter

C Output is 2 as expected

D Memory leak error due to missing free calls

💡 Hint

Check the comparison function used in qsort.

The code uses strcmp as the comparison function for qsort on int arrays, which is invalid and causes undefined behavior or runtime error.

🧠 Conceptual

advanced

Understanding the logic behind minimum meeting rooms calculation

Why does sorting start and end times separately help in calculating the minimum number of meeting rooms required?

A It helps to merge intervals to reduce the number of rooms needed.

B It sorts the meetings by duration to allocate rooms accordingly.

C It groups meetings by their start times to assign rooms in batches.

D It allows us to track when meetings start and end independently to find overlaps efficiently.

💡 Hint

Think about how overlaps are detected by comparing start and end times.

Sorting start and end times separately lets us iterate through meetings in chronological order, comparing the earliest start with the earliest end to detect overlaps and allocate rooms efficiently.

🚀 Application

expert

Calculate minimum meeting rooms for complex intervals

Given the intervals below, what is the minimum number of meeting rooms required?

DSA C

Intervals: [[1, 10], [2, 7], [3, 19], [8, 12], [10, 20], [11, 30]]

A 5

B 4

C 3

D 6

💡 Hint

Count the maximum number of overlapping intervals at any time.

The maximum overlap occurs between times 3 and 7 where four meetings overlap: [1,10], [2,7], [3,19], and [8,12] starts after 7 so not overlapping at 3-7 but overlaps later. Careful tracing shows max overlap is 4.