algorithm - Data structure for handling intervals

Question

I have got a series of time intervals (t_start,t_end), that cannot overlap, i.e.: t_end(i) > t_start(i+1). I want to do the following operations:

1) Add new (Union of) intervals [ {(1,4),(8,10)} U (3,7) = {(1,7),(8,10)} ]
2) Take intervals out [ (1,7) - (3,5) = {(1,3),(5,7)}
3) Checking whether a point or a interval overlaps with an interval in my series (intersection)
4) Finding the first "non-interval" of a minimum length after some point [ {(1,4),(7,8)}: there is a "non-interval" of length 3 between 4 and 7 ].

I want to know good ways of implementing this, with low complexities (log n for all operations would do it).

Related question: Data structure for quick time interval look up

Answer 1

It sounds like you could just use a balanced binary tree of all the boundary times.

For example, represent {(1,4), (8,10), (12,15)} as a tree containing 1, 4, 8, 10, 12, and 15.

Each node needs to say whether it's the start or end of an interval. So:

                          8 (start)
                         /        
                1 (start)         12 (start)
                                   /      
                     4 (end)   10 (end)   15 (end)

(Here all the "end" nodes ended up at the bottom by coincidence.)

Then I think you can have all your operations in O(log n) time. To add an interval:

• Find the start time. If it's already in the tree as a start time, you can leave it there. If it's already in the tree as an end time, you'll want to remove it. If it's not in the tree and it doesn't fall during an existing interval, you'll want to add it. Otherwise you don't want to add it.

• Find the stop time, using the same method to find out if you need to add it, remove it, or neither.

• Now you just want to add or remove the abovementioned start and stop nodes and, at the same time, delete all the existing nodes in between. To do this you only need to rebuild the tree nodes at or directly above those two places in the tree. If the height of the tree is O(log n), which you can guarantee by using a balanced tree, this takes O(log n) time.

(Disclaimer: If you're in C++ and doing explicit memory management, you might end up freeing more than O(log n) pieces of memory as you do this, but really the time it takes to free a node should be billed to whoever added it, I think.)

Removing an interval is largely the same.

Checking a point or interval is straightforward.

Finding the first gap of at least a given size after a given time can be done in O(log n) too, if you also cache two more pieces of information per node:

• In each start node (other than the leftmost), the size of the gap immediately to the left.

• In every node, the size of the largest gap that appears in that subtree.

To find the first gap of a given size that appears after a given time, first find that time in the tree. Then walk up until you reach a node that claims to contain a large enough gap. If you came up from the right, you know this gap is to the left, so you ignore it and keep walking up. Otherwise you came from the left. If the node is a start node, check to see if the gap to its left is large enough. If so, you're done. Otherwise, the large-enough gap must be somewhere to the right. Walk down to the right and continue down until you find the gap. Again, because the height of the tree is O(log n), walking it three times (down, up, and possibly down again) is O(log n).