Dynamic algorithms for monotonic interval scheduling problem

We investigate dynamic algorithms for the interval scheduling problem. We focus on the case when the set of intervals is monotonic. This is when no interval properly contains another interval. We provide two data structures for representing the intervals that allow efficient insertion, removal and various query operations. The first dynamic algorithm, based on the data structure called compatibility forest, runs in amortised time O ( log 2 ⁡ n ) for insertion and removal and O ( log ⁡ n ) for query. The second dynamic algorithm, based on the data structure called linearised tree, runs in time O ( log ⁡ n ) for insertion, removal and query. We discuss differences and similarities of these two data structures through theoretical and experimental results.

Authors

• Alexander Gavruskin
• Bakhadyr Khoussainov
• Mikhail Kokho
• Jiamou Liu The University of Auckland

Keywords

• Interval scheduling
• Dynamic algorithms
• Data structures