$6.$ Problem $7-6($page $188)$ on fuzzy sorting of intervals$\mathrm{.}7-6$ Fuzzy sorting of intervals

Consider a sorting problem in which we do not know the numbers exactly. In$-$

stead, for each number, we know an interval on the real line to which it belongs.

That is$,$ we are given $n$ closed intervals of the form $a_i,b_i,$ where $a_i{b}_i.$ We

wish to fuzzy$-$sort these intervals, i$.$e$.,$ to produce a permutation $($:$i_1,i_2,$dots,$i_n$:$)$ of

the intervals such that for $j=1,2,$dots,$n,$ there exist $c_{j}in[a_{i_j},b_{i_j}]$ satisfying

$c_1{c}_2$cdots$c_n.$

a$.$ Design a randomized algorithm for fuzzy$-$sorting $n$ intervals. Your algorithm

should have the general structure of an algorithm that quicksorts the left end$-$

points $($the $a_i$ values$),$ but it should take advantage of overlapping intervals to

improve the running time. $($As the intervals overlap more and more, the prob$-$

lem of fuzzy$-$sorting the intervals becomes progressively easier. Your algorithm

should take advantage of such overlapping, to the extent that it exists.$)$

b$.$ Argue that your algorithm runs in expected time $(nlgn)$ in general, but runs

in expected time $(n)$ when all of the intervals overlap $($i$.$e$.,$ when there exists a

value $x$ such that xin$[a_i,b_i]$ for all $i).$ Your algorithm should not be checking

for this case explicitly; rather, its performance should naturally improve as the

amount of overlap increases.