Best data structures to store overlapping intervals?

Question

I have different time intervals (contains partial or full overlaps). I provided the sample input and output so that it would be easy to understand.

Sample Input-1: [1-5, 2-3, 3-5, 3-5, 3-6]

Sample Output-1: [(1-2):1, (2-3):2, (3-5):4, (5-6):1]

The above output informs that, for the interval (1-2), there is only one interval (among given inputs) that overlaps. for the interval (2-3), both inputs 1-5 and 2-3 overlap. and so on.

I did a search and found that an interval tree (with slight modifications) could be the best match to store and produce this output. I am here to hear the other's opinion on which could be the more suitable data structure for my use case.

PS:

I don't wish to update/read/delete the tree. Just insert the interval and flat that tree similar to the sample output.

Sample Input-2: [1-2, 3-4, 5-6]

Sample Output-2: [(1-2):1, (3-4):1, (5-6):1]

Sample Input-3: [1-3, 3-4, 5-6]

Sample Output-3: [(1-3):1, (3-4):1, (5-6):1]

Sample Input-4: [1-4, 3-4, 5-6]

Sample Output-4: [(1-2):1, (3-4):2, (5-6):1]

Answer 1

Copy all interval endpoints to a single array, together with a start/end flag and sort on increasing times.

Sample Input-1: [1-5, 2-3, 3-5, 3-5, 3-6]

Sorted list: [1+, 2+, 3-, 3+, 3+, 3+, 5-, 5-, 5-, 6-]

Now by traversing the sorted list, you directly know the numbers of overlapping intervals: [<1:0,1:1,2:2,3:4,5:1,>=6:0] (equal values have been merged).

Answer 2

You can compute the desired output in time $O(n \log n)$, where $n$ is the number of intervals, without any advanced data structure.

For the sake of simplicity suppose that there are no intervals of length $0$ and that the set of all endpoints of the intervals is $\{1,2,\dots,k\}$ with $k=O(n)$. This can be guaranteed w.l.o.g. by performing coordinate compression (sort the times, remove the duplicates, and replace each occurrence of a time $t$ with the rank $r_t$ of $t$. This rank $r_t$ also allows you to recover the original time once you are done) which ensures $k \le 2n$.

Sort the intervals twice, once by their starting time and once by the ending time (this requires time $O(n \log n)$). For each $i \in \{1,\dots,k\}$ let $B_i$ (resp. $E_i$) be the number of intervals that begin (resp. end) not later than point $i$. All $B_i$ and $E_i$ can be found in time $O(n)$ by a linear scan of the sorted intervals.

The output consists of one interval $(i, i+1)$ for each $i \in \{1,\dots,k-1\}$ . The number of input intervals that intersect $(i, i+1)$ is exactly the number of intervals that are "alive" at time $i$, i.e., that begin at some time $\le i$ and end at some time $> i$. Those are exactly $B_i - E_i$.

If the times are integers and their absolute value is upper bounded by $n^k$, for some constant $k$, the sorting step can be performed using the Radix Sort algorithm. This lowers the overall running time to $O(n)$, which is optimal.