0
$\begingroup$

I have a set of (integer) ranges and want to compute the (possibly non-disjoint) set of all subsets of overlapping ranges. The data structure used for the output is not of particular importance to me; if a linked list can be used to reduce the run time, for example, then that's alright with me.

Formal problem

Consider a set of integer ranges $R$. Find the largest set $O = \{ R_i \subset R \}$ where each (non-empty, unique) $R_i$ satisfies $\forall r, r' \in R : r \ \text{overlaps}\ r' \iff r, r' \in R_i$.

What is the algorithm with the lowest known time complexity for solving this problem?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Okay, so I think combination explosion is going to get me whatever way I look at this... the question is whether I can somehow constrain the problem to limit this. $\endgroup$ – Noldorin Sep 10 '18 at 3:07
1
$\begingroup$

Sort the ranges by their start points. Then your overlapping ranges can be found in $O(k + n)$ where $k$ is the number of overlapping pairs and $n$ is the input size simply by a double loop. In C:

int i, j;
for (i = 0; i < n; ++i) {
    int start = start_points[i];
    for (j = i + 1; j < n && start_points[j] < end_points[i]; ++j) {
        output(i, j);
    }
}
|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks. I thought the same thing, but how can I explicitly list groups from this? $\endgroup$ – Noldorin Sep 5 '18 at 18:25

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.