Menu
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
426
An interval is a pair of integers [a,b] such that a < b. The endpoints a and b of each interval [a,b] divide the integer line into partitions called elementary intervals. The interval x=[10, 20] has been added to the integer line.
An interval heap is a complete binary tree in which each node, except possibly the last one (the nodes of the complete binary tree are ordered using a level order traversal), contains two elements.
Interval Tree: The idea is to augment a self-balancing Binary Search Tree (BST) like Red Black Tree, AVL Tree, etc to maintain set of intervals so that all operations can be done in O(Logn) time. Every node of Interval Tree stores following information. b) max: Maximum high value in subtree rooted with this node.
Interval tree is mainly a geometric data structure and often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene.
Without knowing anymore specifics, I'd suggest reading about Interval Trees. Interval trees are a special 1 dimensional case of more generic kd-trees, and have a O(n log n) construction time, and O(log n) typical operation times. Exact algorithm implementations you'd need to find yourself, but you can start by looking at CGAL.
108
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
