7-6 Fuzzy sorting of intervals

Consider the 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 $[a_i, b_i]$, where $a_i \le b_i$. We wish to fuzzy-sort these intervals, i.e., to produce a permutation $\langle i_1, i_2, \ldots, i_n \rangle$ of the intervals such that for $j = 1, 2, \ldots, n$, there exists $c_j \in [a_{i_j}, b_{i_j}]$ satisfying $c_1 \le c_2 \le \cdots \le 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 endpoints (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 problem of fuzzy-sorting the intervals becoes progressively easier. Your algorithm should take advantage of such overlapping, to the extend that it exists.)

b. Argue that your algorithm runs in expected time $\Theta(n\lg n)$ in general, but runs in expected time $\Theta(n)$ when all of the intervals overlap (i.e., when there exists a value $x$ such that $x \in [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.

a.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
FUZZY-PARTITION(A, p, r)
    x = A[r]
    exchange A[r] with A[p]
    i = p - 1
    k = p
    for j = p + 1 to r - 1
        if b[j] < x.a
            i = i + 1
            k = i + 2
            exchange A[i] with A[j]
            exchange A[k] with A[j]
        if b[j]  x.a or a[j]  x.b
            x.a = max(a[j], x.a) and x.b = min(b[j], x.b)
            k = k + 1
            exchange A[k] with A[j]
    exchange A[i + 1] with A[r]
    return i + 1 and k + 1

When intervals overlap we treat them as equal elements, thus cutting down on the time required to sort.

b. For distinct intervals the algorithm runs exactly as regular quicksort does, so its expected runtime will be $\Theta(n\lg n)$ in general. If all of the intervals overlap then the condition on line 12 will be satisfied for every iteration of the for loop. Thus the algorithm returns $p$ and $r$, so only empty arrays remain to be sorted. $\text{FUZZY-PARTITION}$ will only be called a single time, and since its runtime remains $\Theta(n)$, the total expected runtime is $\Theta(n)$.