Dynamic Algorithms for Interval Scheduling on a Single Machine

Alex Gavryushkin, Bakhadyr Khoussainov, Mikhail Kokho +1

We investigate dynamic algorithms for the interval scheduling problem. Our algorithm runs in amortised time $O(\log n)$ for query operation and $O(d{\log }^{2}n)$ for insertion and rem…