Heap review

Questions 1 to 5 of 6

1. 1. This loop runs the min heap method over the meetings {1, 4}, {2, 6}, {4, 5}, {5, 9} and {8, 10}, which are already sorted by start time. ``cpp for (const Meeting& m : meetings) { if (!busyEnds.empty() && busyEnds.top() <= m.start) busyEnds.pop(); busyEnds.push(m.end); cout << "[" << m.start << "," << m.end << ") busy=" << busyEnds.size() << '\n'; } `` What does the line for {4, 5} print?

   [4,5) busy=3[4,5) busy=1[4,5) busy=2[4,5) busy=4
2. 2. What does this program print? ``cpp struct Job { string name; int priority; int seq; }; struct ByPriorityThenSeq { bool operator()(const Job& a, const Job& b) const { if (a.priority != b.priority) return a.priority < b.priority; return a.seq > b.seq; } }; int main() { priority_queue<Job, vector<Job>, ByPriorityThenSeq> pq; int next = 0; auto push = [&](string name, int p) { pq.push({std::move(name), p, next++}); }; push("A", 2); push("B", 1); push("C", 2); push("D", 3); push("E", 2); push("F", 1); while (!pq.empty()) { cout << pq.top().name << ' '; pq.pop(); } cout << '\n'; } ``

   A C E D B FD A E C B FD B F A C ED A C E B F
3. 3. The meeting rooms method checks busyEnds.top() <= m.start before it reuses a room. Which pair of meetings can share one room?

   {9, 11} then {10, 12}, because the second starts before the first ends so they overlap{9, 10} then {10, 11}, because the room is free at 10 and the check uses <={9, 10} then {10, 11}, because the room stays busy until 11{9, 10} then {11, 12}, but only if the check is written with <
4. 4. This code is meant to build a queue that uses a comparator capturing limit. ``cpp int limit = 10; auto cmp = [limit](int a, int b) { return (a % limit) < (b % limit); }; priority_queue<int, vector<int>, decltype(cmp)> pq; `` What goes wrong?

   A lambda with a capture has no default constructor, so the queue cannot build its comparator with no arguments. Pass the object instead, as in pq(cmp).The % operator is not allowed on int, so the comparator will not compile.C++20 does not allow decltype on a lambda, so the type name is invalid.The queue needs greater<int> as its comparator, so the lambda must be replaced with it.
5. 5. Which of these comparator bodies are safe to give to a std::priority_queue? Each one is the body of operator(), with a and b as the two items being compared.

   Pick every answer that is true.

   return a.key < b.key;return a.key <= b.key;return a.score >= b.score;if (a.priority != b.priority) return a.priority < b.priority; return a.seq > b.seq;