# What is the optimal algorithm for finding all sets of overlapping ranges?

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?

• 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. Sep 10, 2018 at 3:07

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;