Consider a sorting problem in which we do not know the numbers exactly. Instead, 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 [ai​, bi​], where ai​≤bi​. We wish to fuzzy-sort these intervals, i.e., to produce a permutation ⟨i1​,i2​,⋯in​⟩ of the intervals such that for j=1,2,⋯,n, there exist cj​∈[aj​,bj​] satisfying c1​≤c2​≤⋯≤cn​.. (a) Design a randomized algorithm for fuzzy-sorting n intervals. Your algorithm should have the general structure of an algorithm that quicksort’s the left endpoints (the ai​values), but it should take advantage of overlapping intervals to improve the running time. (As the intervals overlap more and more, the problem of fuzzy-sorting the intervals becomes progressively easier. Your algorithm should take advantage of such overlapping, to the extent that it exists). (b) What is the best-case runtime for your algorithm? Describe a class of interval arrays that will enjoy this best-case run-time.