Intervals and quickselect in Python

Questions 1 to 5 of 8

1. 1. Put the steps of merging intervals in the order the code runs them.

   Use the arrows to put the steps in order.

   1. 1.For each next interval, set current[1] to max(current[1], end) if it starts at or before current's end; otherwise append current to merged and start a new current from the next interval↑↓
   2. 2.After the loop, append the last current to merged↑↓
   3. 3.Set current to a copy of the first interval with list(ordered[0])↑↓
   4. 4.Sort a copy of the intervals by their start with sorted(intervals, key=lambda iv: iv[0])↑↓
2. 2. Put the steps of one quickselect round in the order they run, from a range to the answer.

   Use the arrows to put the steps in order.

   1. 1.Compare p with k↑↓
   2. 2.If p equals k, return the pivot; otherwise keep only the side that holds index k↑↓
   3. 3.Repeat on the kept side until the range has one item↑↓
   4. 4.Partition the range around a pivot, which gives the pivot its final index p↑↓
3. 3. What does this program print? ``python def merge(intervals): if not intervals: return [] ordered = sorted(intervals, key=lambda iv: iv[0]) merged = [] current = list(ordered[0]) for start, end in ordered[1:]: if start <= current[1]: current[1] = max(current[1], end) else: merged.append(current) current = [start, end] merged.append(current) return merged print(merge([[6, 7], [1, 2], [2, 4], [4, 5]])) print(merge([[3, 9], [1, 2], [5, 6]])) ``

   [[1, 4], [6, 7]] [[1, 2], [3, 9]][[1, 5], [6, 7]] [[1, 2], [3, 9]][[1, 2], [4, 5], [6, 7]] [[1, 2], [3, 9]][[1, 5], [6, 7]] [[1, 9]]
4. 4. What is the first line this program prints? ``python def partition(a, lo, hi): pivot = a[hi] i = lo - 1 for j in range(lo, hi): if a[j] < pivot: i += 1 a[i], a[j] = a[j], a[i] a[i + 1], a[hi] = a[hi], a[i + 1] return i + 1 def quick_select(a, k): lo = 0 hi = len(a) - 1 while lo < hi: p = partition(a, lo, hi) print(f'pivot {a[p]} ends at {p}, array {a}') if p == k: return a[p] if k < p: hi = p - 1 else: lo = p + 1 return a[lo] print(f'result: {quick_select([5, 3, 8, 1, 9, 2], 3)}') ``

   pivot 9 ends at 4, array [5, 3, 8, 1, 2, 9]pivot 2 ends at 0, array [2, 3, 8, 5, 9, 1]pivot 3 ends at 1, array [1, 3, 8, 5, 9, 2]pivot 2 ends at 1, array [1, 2, 8, 5, 9, 3]
5. 5. Run on the sorted intervals [[1, 10], [2, 3], [4, 5]], this loop gives [[1, 3], [4, 5]] instead of [[1, 10]]. What is the bug? ``python current = list(ordered[0]) for start, end in ordered[1:]: if start <= current[1]: current[1] = end else: merged.append(current) current = [start, end] merged.append(current) ``

   It compares start with current[0] instead of current[1]It is missing merged.append(current) after the loopIt sets current[1] to end, so a short interval inside current shrinks it; it should keep the larger end with max(current[1], end)It should use < instead of <= so touching intervals stay separate