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.

Practice

1. What does the "Meeting Rooms Problem Minimum Rooms Required" ask you to find given a list of meeting time intervals?

easy

A. The minimum number of meeting rooms needed to hold all meetings without overlap

B. The maximum duration of a single meeting

C. The total number of meetings scheduled

D. The earliest start time among all meetings

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of rooms needed so that no two meetings overlap in the same room.

2. Step 2: Clarify what is asked

   We want to find how many rooms are needed to schedule all meetings without time conflicts.

3. Final Answer:

   The minimum number of meeting rooms needed to hold all meetings without overlap -> Option A

4. Quick Check:

   Minimum rooms = no overlapping meetings at the same time [OK]

Hint: Count max overlapping meetings to find minimum rooms [OK]

Common Mistakes:

• Confusing total meetings with rooms needed
• Thinking about meeting durations instead of overlaps
• Ignoring overlapping intervals

2. Which of the following C code snippets correctly declares an array of meeting intervals where each interval has a start and end time?

easy

A. int intervals[2][3] = {{0, 5, 15}, {30, 10, 20}};

B. int intervals[3] = {0, 30, 5, 10, 15, 20};

C. int intervals[3][2] = {0, 30, 5, 10, 15, 20};

D. int intervals[3][2] = {{0, 30}, {5, 10}, {15, 20}};

Solution

1. Step 1: Check array dimensions and initialization

   We need a 2D array with 3 intervals, each having 2 values (start and end).

2. Step 2: Validate each option

   int intervals[3][2] = {{0, 30}, {5, 10}, {15, 20}}; correctly declares int intervals[3][2] with proper nested braces for each interval.

3. Final Answer:

   int intervals[3][2] = {{0, 30}, {5, 10}, {15, 20}}; -> Option D

4. Quick Check:

   Correct 2D array syntax for intervals [OK]

Hint: Use int arr[n][2] for intervals with start and end [OK]

Common Mistakes:

• Using 1D array for 2D interval data
• Incorrect brace nesting in initialization
• Swapping rows and columns in declaration

3. Given the following C code snippet, what is the output printed?

int intervals[3][2] = {{0, 30}, {5, 10}, {15, 20}};
// Assume a function minMeetingRooms(intervals, 3) returns minimum rooms needed
int rooms = minMeetingRooms(intervals, 3);
printf("%d\n", rooms);

Assuming minMeetingRooms correctly implements the meeting rooms logic, what is printed?

medium

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Analyze meeting intervals for overlaps

   Intervals: [0,30], [5,10], [15,20]. The first and second overlap (5 < 30), so need at least 2 rooms.

2. Step 2: Check if any three overlap simultaneously

   Third interval [15,20] overlaps with first [0,30], but second ends at 10, so max overlap is 2 meetings at once.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Max overlapping meetings = 2 [OK]

Hint: Count max overlaps to find rooms needed [OK]

Common Mistakes:

• Assuming all meetings overlap simultaneously
• Counting total meetings instead of overlaps
• Ignoring partial overlaps

4. The following C function aims to find the minimum number of meeting rooms required but has a bug. What is the bug?

int minMeetingRooms(int intervals[][2], int n) {
    int rooms = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {
                rooms++;
            }
        }
    }
    return rooms;
}

medium

A. It counts overlapping pairs but does not track maximum overlaps for rooms

B. It uses wrong indices in the loops causing out-of-bounds access

C. It returns zero always because rooms is never incremented

D. It sorts intervals incorrectly before counting overlaps

Solution

1. Step 1: Understand the nested loops and condition

   The code counts each overlapping pair by checking if intervals overlap and increments rooms.

2. Step 2: Identify why counting pairs is incorrect

   Counting pairs does not give the minimum rooms needed; we need the maximum number of simultaneous overlaps.

3. Final Answer:

   It counts overlapping pairs but does not track maximum overlaps for rooms -> Option A

4. Quick Check:

   Counting pairs ≠ max simultaneous overlaps [OK]

Hint: Track max overlaps, not just count pairs [OK]

Common Mistakes:

• Confusing pair counts with room count
• Not sorting intervals before processing
• Ignoring simultaneous overlaps

5. You have the following meeting intervals: [[1, 4], [2, 5], [7, 9], [3, 6], [10, 11]]. Using the minimum rooms required approach, what is the minimum number of meeting rooms needed?

hard

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Sort intervals by start time

   Sorted intervals: [1,4], [2,5], [3,6], [7,9], [10,11]

2. Step 2: Find maximum overlapping meetings

   Between 1-6, three meetings overlap: [1,4], [2,5], [3,6]. After 6, meetings do not overlap.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Max overlaps = 3 rooms needed [OK]

Hint: Sort intervals, count max overlaps for rooms [OK]

Common Mistakes:

• Not sorting intervals before counting
• Counting total meetings instead of overlaps
• Missing overlapping intervals in middle