Intersecting lists of intervals

Some evenings I like to sit at home, make myself a tea, and start working on random problems that pop into my head or that I find through various contexts. I force myself NOT to look on stackoverflow or wikipedia for a copy-paste solution because I enjoy bashing my head against something that I don’t know how to solve.

A few days ago I started thinking about the following problem.
Let’s say we have a list of intervals, each interval corresponding to a ID. Something like this:
ID 0 : [start0, end0], [start1, end1], [start2, end2]
ID 1 : [start3, end3], [start4, end4]

Given a query made up of one or more IDs, how can we return the intervals that contain ALL the IDs specified in the query.
We need to return only the overlapping parts of the intervals.

Continue reading “Intersecting lists of intervals”