I have a collection of time intervals with integer valued endpoints , e.g. (1,2), (2, 6) (5,6), and the number of events falling in each time interval, and I would like to determine if from them I can extract a mutually exclusive set of intervals covering the same period, in this case (1,2), (2, 5), (5,6), where the number of events falling in (2,5) is calculated by taking the difference of the number in (2,6) and (5,6). There is no limit on the number of possible overlaps, e.g they could all be of the form (n, 24). I would like to know if this is a standard problem with a standard solution.
closed as off-topic by Geoff Oxberry Jul 30 '15 at 0:32
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "General computer science questions are off-topic here, but can be asked on Computer Science Stack Exchange." – Geoff Oxberry
I don't know of a standard name for the problem as you describe it but you can use a standard data structure to solve the problem: interval tree
You can sequentially insert each interval into the tree, but only insert those parts of the interval that are disjoint from any intervals already inserted in the tree. That way as you build the tree you are guaranteed that only mutually exclusive intervals are in the tree. Interval trees are designed to quickly search for overlapping intervals so all this searching should not be a problem.
Here's an algorithm to do it:
- Let T be an interval tree (initially empty)
- Let L be the list of intervals
- Pop an interval I from L
- Query T for a list of intervals O overlapping I
- Intersect I with each interval in O. For each non-empty intersection remove that intersection from I (this will make I very disjoint) and update the event count of the interval in O with the event count from I.
- Add any remaining non-overlapping intervals from I to T
- If L is non-empty go to Step 3 else go to Step 8
- Query T for all the intervals.
The final step gives you your list of mutually exclusive intervals with the appropriate event counts.
Note, the way you update the event count will require some experimenting. For example, you may only want to update the event count in the overlapping intervals of O with a proportion of the event count in I that overlapped and not the raw count.