Intervals and quickselect

Questions 1 to 5 of 8

1. 1. Put the steps of one round of the quickselect loop in the correct order, from start to finish.

   Use the arrows to put the steps in order.

   1. 1.If k is smaller than p, set hi = p - 1. Otherwise set lo = p + 1.↑↓
   2. 2.Go back to the top of the loop and repeat with the smaller range.↑↓
   3. 3.If p equals k, return a[p], because the pivot is the answer.↑↓
   4. 4.Partition the range lo to hi around its last value, and note the pivot's final index p.↑↓
2. 2. What does this program print? ``cpp #include <algorithm> #include <iostream> #include <vector> struct Interval { int start; int end; }; std::vector<Interval> merge_intervals(std::vector<Interval> intervals) { std::vector<Interval> merged; if (intervals.empty()) { return merged; } std::sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) { return a.start < b.start; }); merged.push_back(intervals[0]); for (std::size_t i = 1; i < intervals.size(); ++i) { Interval& last = merged.back(); if (intervals[i].start <= last.end) { last.end = std::max(last.end, intervals[i].end); } else { merged.push_back(intervals[i]); } } return merged; } void print(const std::vector<Interval>& list) { std::cout << "["; for (std::size_t i = 0; i < list.size(); ++i) { std::cout << (i ? ", " : "") << "[" << list[i].start << ", " << list[i].end << "]"; } std::cout << "]\n"; } int main() { print(merge_intervals({{2, 5}, {1, 2}, {6, 7}, {7, 9}})); } ``

   [[1, 2], [2, 5], [6, 7], [7, 9]][[1, 5], [6, 9]][[1, 9]][[1, 5], [6, 7], [7, 9]]
3. 3. Put the steps of free_time in the correct order, from start to finish.

   Use the arrows to put the steps in order.

   1. 1.For each merged block, add a gap from cursor to the block's start if the block starts after cursor, then move cursor to the larger of cursor and the block's end.↑↓
   2. 2.After the loop, add a gap from cursor to the end of the day if cursor is before it.↑↓
   3. 3.Set cursor to the start of the day.↑↓
   4. 4.Merge the busy intervals with merge_intervals, so they are sorted and do not overlap.↑↓
4. 4. What does this program print? ``cpp #include <algorithm> #include <iostream> #include <vector> struct Interval { int start; int end; }; std::vector<Interval> merge_intervals(std::vector<Interval> intervals) { std::vector<Interval> merged; if (intervals.empty()) { return merged; } std::sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) { return a.start < b.start; }); merged.push_back(intervals[0]); for (std::size_t i = 1; i < intervals.size(); ++i) { Interval& last = merged.back(); if (intervals[i].start <= last.end) { last.end = std::max(last.end, intervals[i].end); } else { merged.push_back(intervals[i]); } } return merged; } std::vector<Interval> free_time(const std::vector<Interval>& busy, int day_start, int day_end) { std::vector<Interval> gaps; int cursor = day_start; for (const Interval& b : merge_intervals(busy)) { if (b.start > cursor) { gaps.push_back({cursor, b.start}); } cursor = std::max(cursor, b.end); } if (cursor < day_end) { gaps.push_back({cursor, day_end}); } return gaps; } void print(const std::vector<Interval>& list) { std::cout << "["; for (std::size_t i = 0; i < list.size(); ++i) { std::cout << (i ? ", " : "") << "[" << list[i].start << ", " << list[i].end << "]"; } std::cout << "]\n"; } int main() { print(free_time({{10, 12}, {11, 13}}, 9, 15)); } ``

   [[9, 13]][[10, 13]][[9, 10], [13, 15]][[9, 10], [11, 13], [13, 15]]
5. 5. The merge loop below should join intervals that touch at one number, such as [1, 4] and [4, 5]. What does it print for the input {{1, 4}, {4, 5}}, and what is the fix? ``cpp merged.push_back(intervals[0]); for (std::size_t i = 1; i < intervals.size(); ++i) { Interval& last = merged.back(); if (intervals[i].start < last.end) { last.end = std::max(last.end, intervals[i].end); } else { merged.push_back(intervals[i]); } } ``

   [[1, 5]]. The strict < is the right rule for closed intervals, so nothing is wrong.[[1, 4], [4, 5]]. The check should be <=, because the closed interval [1, 4] contains 4, so it overlaps [4, 5].[[1, 4]]. The check should be >=, so the second interval is dropped.[[4, 5]]. The sort should be by end, so [4, 5] comes first.