Dynamic Algorithms for Interval Scheduling on a Single Machine

الأصل · EN

We investigate dynamic algorithms for the interval scheduling problem. Our algorithm runs in amortised time O(n) for query operation and O(d² n) for insertion and removal operations, where n and d are the maximal numbers of intervals and pairwise overlapping intervals respectively. We also show that for a monotonic set, that is when no interval properly contains another interval, the amortised complexity is O(n) for both query and update operations. We compare the two algorithms for the monotonic interval sets using experiments.