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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum meeting rooms required

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

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int minMeetingRooms(vector<pair<int,int>>& intervals) {
    if(intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end(), [](auto &a, auto &b){ return a.first < b.first; });
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(intervals[0].second);
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i].first >= minHeap.top()) {
            minHeap.pop();
        }
        minHeap.push(intervals[i].second);
    }
    return minHeap.size();
}

int main() {
    vector<pair<int,int>> intervals = {{0, 30}, {5, 10}, {15, 20}};
    cout << minMeetingRooms(intervals) << endl;
    return 0;
}

A 3

B 0

C 1

D 2

💡 Hint

Think about how many meetings overlap at the same time.

The code sorts intervals by start time and uses a min-heap to track the earliest ending meeting. It pops from the heap when a meeting room is freed. The maximum heap size is the minimum rooms needed. Here, two meetings overlap, so 2 rooms are needed.

❓ Predict Output

intermediate

Minimum rooms for non-overlapping meetings

What is the output of this code for intervals with no overlaps?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int minMeetingRooms(vector<pair<int,int>>& intervals) {
    if(intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end(), [](auto &a, auto &b){ return a.first < b.first; });
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(intervals[0].second);
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i].first >= minHeap.top()) {
            minHeap.pop();
        }
        minHeap.push(intervals[i].second);
    }
    return minHeap.size();
}

int main() {
    vector<pair<int,int>> intervals = {{1, 5}, {6, 10}, {11, 15}};
    cout << minMeetingRooms(intervals) << endl;
    return 0;
}

A 1

B 0

C 3

D 2

💡 Hint

No meetings overlap, so only one room is needed.

Since all meetings are sequential without overlap, only one room is needed.

🔧 Debug

advanced

Identify the error in meeting rooms calculation

What error will this code produce when run?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int minMeetingRooms(vector<pair<int,int>>& intervals) {
    if(intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(intervals[0].second);
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i].first >= minHeap.top()) {
            minHeap.pop();
        }
        minHeap.push(intervals[i].second);
    }
    return minHeap.size();
}

int main() {
    vector<pair<int,int>> intervals = {{0, 30}, {5, 10}, {15, 20}};
    cout << minMeetingRooms(intervals) << endl;
    return 0;
}

A Compilation error due to sort call

B No error, output is 2

C Runtime error: accessing empty heap

D Wrong output: 3 instead of 2

💡 Hint

Check if sort call is valid for vector>.

The default sort for pairs sorts by first element then second, so sort(intervals.begin(), intervals.end()) is valid. No error occurs and output is correct.

❓ Predict Output

advanced

Minimum rooms required with overlapping intervals

What is the output of this code for intervals with multiple overlaps?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int minMeetingRooms(vector<pair<int,int>>& intervals) {
    if(intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end(), [](auto &a, auto &b){ return a.first < b.first; });
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(intervals[0].second);
    for(int i = 1; i < intervals.size(); i++) {
        if(intervals[i].first >= minHeap.top()) {
            minHeap.pop();
        }
        minHeap.push(intervals[i].second);
    }
    return minHeap.size();
}

int main() {
    vector<pair<int,int>> intervals = {{1, 10}, {2, 7}, {3, 19}, {8, 12}, {10, 20}, {11, 30}};
    cout << minMeetingRooms(intervals) << endl;
    return 0;
}

A 5

B 3

C 4

D 6

💡 Hint

Count the maximum number of overlapping meetings at any time.

The maximum overlap is 4 meetings at once, so minimum rooms required is 4.

🧠 Conceptual

expert

Why use a min-heap in Meeting Rooms problem?

Why is a min-heap used to solve the Meeting Rooms problem efficiently?

A To always know the earliest meeting end time to free a room quickly

B To sort meetings by start time before processing

C To store all meeting start times for quick access

D To count total meetings without overlap

💡 Hint

Think about how to reuse rooms as soon as possible.

The min-heap keeps track of the earliest finishing meeting so we can free that room if the next meeting starts after it ends, minimizing rooms used.

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 maximum length of a single meeting

B. The total number of meetings scheduled

C. The minimum number of rooms needed so no meetings overlap

D. The earliest meeting start time

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 being counted

   We count how many meetings happen at the same time to find the minimum rooms required.

3. Final Answer:

   The minimum number of rooms needed so no meetings overlap -> Option C

4. Quick Check:

   Minimum rooms = max overlapping meetings [OK]

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

Common Mistakes:

• Confusing total meetings with rooms needed
• Thinking earliest start time is the answer
• Ignoring overlapping intervals

2. Which of the following C++ code snippets correctly sorts a vector of meeting intervals by their start time? Assume intervals is a vector of pairs where first is start and second is end time.

easy

A. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.first > b.first; });

B. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.first < b.first; });

C. std::sort(intervals.rbegin(), intervals.rend());

D. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.second < b.second; });

Solution

1. Step 1: Identify sorting by start time

   We want to sort intervals by their start time, which is stored in a.first.

2. Step 2: Check lambda comparator correctness

   std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.first < b.first; }); uses a lambda comparing a.first < b.first, which sorts ascending by start time correctly.

3. Final Answer:

   std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.first < b.first; }); -> Option B

4. Quick Check:

   Sort by start time ascending [OK]

Hint: Sort intervals by start time using lambda with a.first < b.first [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Using default sort without comparator (may sort by first but not guaranteed)
• Sorting descending when ascending is needed

3. What is the output of the following C++ code snippet that calculates the minimum number of meeting rooms required?

std::vector> intervals = {{0,30}, {5,10}, {15,20}};
std::vector<int> starts, ends;
for(auto &i : intervals) {
    starts.push_back(i.first);
    ends.push_back(i.second);
}
std::sort(starts.begin(), starts.end());
std::sort(ends.begin(), ends.end());
int rooms = 0, end_ptr = 0;
for(int i = 0; i < starts.size(); i++) {
    if(starts[i] < ends[end_ptr]) rooms++;
    else end_ptr++;
}
std::cout << rooms << std::endl;

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Sort start and end times

   Starts = [0,5,15], Ends = [10,20,30]

2. Step 2: Iterate and count rooms

   i=0: 0<10 true rooms=1
   i=1: 5<10 true rooms=2
   i=2: 15<10 false end_ptr=1 rooms=2

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Max overlapping meetings = 2 [OK]

Hint: Compare starts and ends with two pointers to count rooms [OK]

Common Mistakes:

• Not sorting start and end arrays
• Incrementing rooms incorrectly
• Confusing when to move end pointer

4. The following code attempts to find the minimum number of meeting rooms needed but has a bug. What is the bug?

std::vector> intervals = {{1,5}, {2,6}, {8,10}};
std::sort(intervals.begin(), intervals.end());
int rooms = 1;
for(int i = 1; i < intervals.size(); i++) {
    if(intervals[i].first < intervals[i-1].second) rooms++;
}
std::cout << rooms << std::endl;

medium

A. The loop should start from i = 0, not i = 1

B. The intervals vector is not sorted correctly

C. The rooms variable should start at 0, not 1

D. It only compares each meeting with the previous one, missing overlaps with earlier meetings

Solution

1. Step 1: Analyze overlap check logic

   The code only checks if current meeting starts before previous meeting ends, ignoring overlaps with other meetings.

2. Step 2: Understand why this causes error

   This misses cases where a meeting overlaps with a meeting before the previous one, undercounting rooms needed.

3. Final Answer:

   It only compares each meeting with the previous one, missing overlaps with earlier meetings -> Option D

4. Quick Check:

   Check all overlaps, not just adjacent meetings [OK]

Hint: Check overlaps with all active meetings, not just previous [OK]

Common Mistakes:

• Assuming sorting fixes all overlap checks
• Starting loop at wrong index
• Incorrect initial rooms count

5. Given the following meeting intervals: {{0, 10}, {5, 15}, {10, 20}, {15, 25}, {20, 30}}, what is the minimum number of meeting rooms required to schedule all meetings without overlap?

hard

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Sort start and end times

   Starts = [0,5,10,15,20], Ends = [10,15,20,25,30]

2. Step 2: Use two pointers to count rooms

   i=0: 0<10 rooms=1
   i=1: 5<10 rooms=2
   i=2: 10<10 false end_ptr=1 rooms=2
   i=3: 15<15 false end_ptr=2 rooms=2
   i=4: 20<20 false end_ptr=3 rooms=2

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Max overlapping meetings = 2 [OK]

Hint: Track starts and ends with pointers to find max overlaps [OK]

Common Mistakes:

• Counting all meetings as overlapping
• Not moving end pointer correctly
• Misreading intervals causing wrong overlaps