6
$\begingroup$

I need an efficient algorithm that takes input a collection of intervals and outputs the largest subset of non-intersecting intervals.

i.e. Given a set of intervals $I = \{I_1, I_2, \ldots, I_n\}$ of the real line, we need to output a set of intervals $O = \{O_1, O_2, \ldots, O_k\}$ such that

  • $O$ is a subset of $I$.
  • For any $i \neq j$, $O_i$ and $O_j$ are non-intersecting.
  • $k$ is the maximum possible.

Example: if the intervals are $[1,100], [2,3], [4,5], [6,7], [3,20]$ we should return $\{[2,3], [4,5], [6,7]\}$.

$\endgroup$
  • $\begingroup$ Do you want the least amount of unused time, or the most amount of intervals? Also, does it need to be greedy? $\endgroup$ – tjameson Mar 23 '13 at 3:07
  • $\begingroup$ Input:{ I1, I2,…, In} Output is a collection O=(O1, O2,…On) which is a subset of I, where Oi∩Ok for all {Oj, Ok} ϵ O. Oj≠Ok, and O is the largest of such set. $\endgroup$ – user2112791 Mar 23 '13 at 3:10
  • $\begingroup$ are the intervals always specified as integers? if this is true and the max integer is not large this can be related to a set problem where the intervals are represented by sets of contiguous integers... $\endgroup$ – vzn Mar 24 '13 at 19:56
6
$\begingroup$

There is an $O(n \log n)$ time algorithm (which in some models is optimal, because of the bounds for the element distinctness problem).

We first sort the intervals by their right end point. Suppose the sorted order is $I_1, I_2, \ldots, I_n$.

Now for each interval, we try to compute the size of the largest possible non-intersecting set, with that interval being the rightmost interval in that set. We pick the interval which gives the maximum (as any non-intersecting set has a rightmost interval).

This we do using dynamic programming.

Suppose we have computed the sizes (say $S_1, \ldots, S_n$) for intervals up to $k-1$. Now you want to compute for $I_k = [L_k, R_k]$.

Pick $L_k$, and do a binary search in $[R_1,R_2, \ldots, R_k]$. Say $R_j \lt L_k \lt R_{j+1}$.

Now all the intervals $1,2,\ldots,j$ do not intersect $I_k$ (and all others up to $I_{k-1} \cap I_k$). Thus we need to pick the max among $S_1, S_2, \ldots, S_j$ and add $1$ to it. This maximum can also be computed dynamically, in a separate array, along with the $S$.

This can be implemented so that the whole algorithm runs in $O(n \log n)$.

We can also modify this algorithm a little to give you the actual intervals which form the non-intersecting set.

$\endgroup$
5
$\begingroup$

This is called the "Interval Scheduling" problem in the book [1]. The greedy algorithm, along with an example, is as follows (please find the correctness proof in the book mentioned above):

  • sort the intervals in increasing order of their finishing times, still denoted as $\mathcal{I}$.
  • while ($\mathcal{I} \neq \emptyset$) choose the first $I \in \mathcal{I}$, do:
    • add $I$ into the result-set; (darker lines in the figure)
    • delete all intervals from $\mathcal{I}$ that conflicts with $I$ (dashed lines in the figure).

interval-scheduling-example

[1]: Algorithm Design. By Jon Kleinberg and Éva Tardos. (Section 4.1)

$\endgroup$

Your Answer

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