Let $x$ be a set of $n$ intervals on the real line. A set of points $P$ stabs $x$ if every interval in $x$

contains at least one points in $P.$ Note that for each interval, both end points are considered

contained in the interval. Given the arrays $x_L[1,$dots,$n]$ and $x_R[1,$dots,$n]$ specifying the left and

right end points of the intervals, we want to design a greedy algorithm that computes the

smallest set of points stabbing $x.$ Hint: review the interval scheduling problem and the greedy

stays ahead argument.

Figure $1$: A set of intervals stabbed by $3$ points.

$($a$)$ Here is a possible greedy rule: find a point that stabs the maximum number of intervals,

remove the stabbed intervals and repeat. Show a counter example demonstrating that the

rule is not optimal or prove that the rule is optimal.

Solution:

$($b$)$ Here is a possible greedy rule: pick the smallest right end point among remaining inter$-$

vals, remove the stabbed intervals and repeat. Show a counter example demonstrating

that the rule is not optimal or prove that the rule is optimal. Hint: use a greedy stays

ahead argument to show that the greedy choice is always greater than or equal to the

corresponding alternative choice.

Solution:

$($c$)$ Give pseudocode implementing your algorithm as fast as possible. Analyze the running

time. You can make calls to algorithms we learned in the course e$.$g$.$ Karatsuba, mergesort,

etc.