Meeting rooms

Questions 1 to 5 of 6

1. 1. What does this program print? Separate the two output lines with / . ``cpp #include <algorithm> #include <functional> #include <iostream> #include <queue> #include <vector> struct Meeting { int start; int end; }; int minRooms(std::vector<Meeting> meetings, bool strict) { std::sort(meetings.begin(), meetings.end(), [](const Meeting& a, const Meeting& b) { return a.start < b.start; }); std::priority_queue<int, std::vector<int>, std::greater<int>> busyEnds; int best = 0; for (const Meeting& m : meetings) { bool freed = !busyEnds.empty() && (strict ? busyEnds.top() < m.start : busyEnds.top() <= m.start); if (freed) { busyEnds.pop(); } busyEnds.push(m.end); best = std::max(best, static_cast<int>(busyEnds.size())); } return best; } int main() { std::vector<Meeting> meetings = {{1, 3}, {3, 5}, {5, 7}}; std::cout << "<=: " << minRooms(meetings, false) << "\n"; std::cout << "<: " << minRooms(meetings, true) << "\n"; } ``

   <=: 2 / <: 1<=: 2 / <: 2<=: 1 / <: 2<=: 1 / <: 1
2. 2. What does this program print? Separate the two output lines with / . ``cpp #include <algorithm> #include <iostream> #include <vector> struct Meeting { int start; int end; }; int minRoomsSweep(const std::vector<Meeting>& meetings) { std::vector<int> starts; std::vector<int> ends; for (const Meeting& m : meetings) { starts.push_back(m.start); ends.push_back(m.end); } std::sort(starts.begin(), starts.end()); std::sort(ends.begin(), ends.end()); int i = 0; int j = 0; int rooms = 0; int best = 0; while (i < static_cast<int>(starts.size())) { if (starts[i] < ends[j]) { ++rooms; ++i; best = std::max(best, rooms); } else { --rooms; ++j; } } return best; } int main() { std::vector<Meeting> first = {{0, 10}, {1, 5}, {6, 8}, {7, 9}}; std::vector<Meeting> second = {{2, 4}, {4, 6}, {6, 8}}; std::cout << "first: " << minRoomsSweep(first) << "\n"; std::cout << "second: " << minRoomsSweep(second) << "\n"; } ``

   first: 2 / second: 1first: 3 / second: 2first: 4 / second: 2first: 3 / second: 1
3. 3. In the heap method, what does busyEnds.top() hold while the heap is not empty?

   The smallest end time among the busy roomsThe largest end time among the busy roomsThe start time of the newest meetingThe number of rooms in use
4. 4. Why does the heap method sort the meetings by start time before the loop?

   So the heap becomes a min-heap, because sorting sets its orderSo that the loop sees meetings in time order, and each one checks only the rooms that are busy at its start timeSo the largest end time is on top when the loop beginsSo the sweep can count rooms, which the heap method cannot do
5. 5. A list has 1,000,000 meetings, and at most 3 rooms are busy at any time. Each heap push or pop costs about log2(k) steps, where k is the number of busy rooms. Using a base-2 logarithm, what is log2(3), rounded to two decimal places?

   Type a number.