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

Question

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?

Answer 1

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);
    }
}