1
$\begingroup$

I am reading this book and am at a point when the Interval Partitioning Problem is discussed. The pseudocode they provide for it is the following:

Sort the intervals by their start times, breaking ties arbitrarily
Let I_1, I_2, ..., I_n denote the intervals in this order
For j = 1, 2, 3, ..., n
    For each interval I_i that precedes I_j in sorted order and overlaps it
        Exclude the label of I_i from consideration for I_j
    Endfor
    If there is any label from {1, 2, ..., d} that has not been excluded then
        Assign a nonexcluded label to I_j
    Else
        Leave I_j unlabeled
    Endif
Endfor

Here n is the number of intervals and d is the depth of the intervals (the maximum number of overlapping intervals)

What I don't understand is why sort the intervals in the first place. I think the algorithm would work even without this step. In other words, it would work no matter the order of I_1, I_2, ..., I_n. Am I correct? Is there something I am missing?

EDIT: Doesn't the algorithm below also produce an interval partitioning, but with the advantage of being faster because no sorting is performed?

Let I_1, I_2, ..., I_n be an arbitrary ordering of the intervals.
For j = 1, 2, ..., n
    For each interval I_i where 1 <= i < j which overlaps with I_j
        Exclude the label of I_i from consideration for I_j
    Endfor
    If there is any label from {1, 2, ..., d} that has not been excluded then
        Assign a nonexcluded label to I_j
    Else
        Leave I_j unlabeled
    Endif
Endfor
$\endgroup$
1
$\begingroup$
  1. Why sorting? One reason is efficiency: the algorithm can easily be improved to run in time $O(nd + n \log n)$ instead of $O(n^2)$. The other reason is that it is not immediately clear (at least not to me) what label to assign to intervals when processing them out of order: you may get yourself stuck later on.

    Here is why it's faster: By iterating over the intervals in order of increasing start time, we can limit the inner for-loop to d iterations. Since all intervals that precede I_j have already been considered in an iteration of the outer for-loop before the current iteration, we know these intervals are already 'scheduled': they have a label assigned to them. Since there are only d labels, there are only d intervals (namely the latest for each label) that can possibly overlap with I_j. The inner for-loop only needs to look at these d intervals for each iteration of the outer for-loop, resulting in a total running time of $O(nd)$ after sorting ($O(n \log n)$ time).

    The line For each interval I_i that precedes I_j in sorted order and overlaps it does not clearly capture this. Instead the algorithm should keep track of the set of intervals containing for each label the most recently encountered interval labelled as such. The inner for-loop should iterate over this set, containing only $d$ intervals.

  2. Your second algorithm in it's current form is not correct, in that it does not always find an optimal solution. Consider the three intervals $\{(1,2),(3,4),(1,4)\}$ which can be partitioned in two sets of pairwise disjoint intervals: $\{(1,2),(3,4)\}$ and $\{(1,4)\}$, i.e. the algorithm should find a label for all intervals when $d=2$. When your second algorithm takes these intervals in order $\langle(1,2),(3,4),(1,4)\rangle$ it may do the following:

    1. For interval $(1,2)$ labels 1 and 2 are available (none of the preceding intervals overlap, because there are no preceding intervals). We choose label 1.
    2. For interval $(3,4)$ labels 1 and 2 are available (none of the preceding intervals ($\{(1,2)\}$) overlap). We choose label 2.
    3. For interval $(1,4)$ all preceding intervals overlap, no labels are available. The algorithm fails to label this interval.
$\endgroup$
  • $\begingroup$ Yes, my algorithm is not equivalent (will fix the wording) but it still produces a valid interval partitioning (it still produces d labels and each interval is assigned a label and there are no conflicts between any 2 intervals having the same label). Also, I don't see how the first algorithm is O(n log(n)), because the outer for-loop takes O(n ^ 2) time. When the authors say "For each interval I_i that precedes I_j in sorted order..." we have to consider {I_1 ... I_(j-1)}. $\endgroup$ – alexgiorev Jul 3 '19 at 16:08
  • $\begingroup$ I have updated my answer to address your comments. $\endgroup$ – kroppyer Jul 4 '19 at 12:25
0
$\begingroup$

Efficiency considerations. Nested for loop shall traverse overlapping intervals, started earlier, then given one. If you will not pre-sort intervals, you will need traverse whole set to look them up.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.