Balloons and intervals

Questions 1 to 5 of 8

1. 1. What does this program print? ``cpp #include <algorithm> #include <iostream> #include <utility> #include <vector> using namespace std; int main() { vector<pair<int, int>> balloons{{1, 4}, {5, 9}, {2, 6}}; sort(balloons.begin(), balloons.end(), [](const auto& a, const auto& b) { return a.second < b.second; }); vector<int> shots; for (const auto& [start, end] : balloons) { if (shots.empty() || start > shots.back()) { shots.push_back(end); } } cout << shots.size() << ' ' << shots.back() << '\n'; } ``

   2 42 91 93 9
2. 2. This program prints one merged block per line. In the options, a slash marks the start of a new line. What does it print? ``cpp #include <algorithm> #include <iostream> #include <vector> using namespace std; struct Interval { int start; int end; }; int main() { vector<Interval> items{{5, 7}, {1, 2}, {2, 4}, {9, 9}}; sort(items.begin(), items.end(), [](const Interval& a, const Interval& b) { return a.start < b.start; }); vector<Interval> merged; for (const Interval& it : items) { if (merged.empty() || it.start > merged.back().end) { merged.push_back(it); } else { merged.back().end = max(merged.back().end, it.end); } } for (const Interval& m : merged) { cout << m.start << '-' << m.end << '\n'; } } ``

   1-2 / 5-7 / 9-91-4 / 5-91-4 / 5-7 / 9-91-2 / 2-4 / 5-7 / 9-9
3. 3. Two balloons are [1, 3] and [3, 5]. The arrow program is changed so that a new arrow is shot when b.start >= shots.back() instead of b.start > shots.back(). How many arrows are shot, and where?

   arrows: 1, arrow at 3arrows: 2, arrows at 3 and 5arrows: 2, arrows at 1 and 5arrows: 1, arrow at 5
4. 4. In the proof that the balloon greedy is optimal, why can the first arrow move from its spot x to the smallest right end e1 without popping fewer balloons?

   The balloons are already sorted, so the arrow can move without checking any balloonThe arrow moves to the largest right end, so it reaches every balloon in the listMoving an arrow right always pops more balloons, so the count can only fallEach balloon the arrow popped at x starts at or before e1 and ends at or after e1, so it is still popped at e1
5. 5. Which statements about the balloon arrow program are true? Pick all that apply.

   Pick every answer that is true.

   Sorting by right end is part of the rule, and sorting by left end can need more arrows than the minimumThe shots.empty() test stops back() from being called on an empty vectorSorting by left end gives the same arrow count as sorting by right end on every inputThe comparator a.end < b.end gives the strict order that sort needsChanging > to >= makes touching balloons share one arrow