Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 8 / e / Solution

Sort once by nondecreasing end time, then retain the most recent meeting:When an interval is inspected, $\text{lastMeeting}\le e$ because of the sorted end order. Therefore the interval is already covered exactly when $s\le \text{lastMeeting}$; otherwise it is the earliest-ending uncovered interval and the algorithm chooses its end. This proves that the scan implements greedy strategy 2. The strict test s > lastMeeting correctly treats equality as covered for closed intervals.

The sorting costs $O(n\log n)$ comparisons, and the scan costs $O(n)$, with $O(k)$ space for the output and constant scan state. Including an empty input, the overall bound is $O(n\log (n+1))$ time, conventionally $O(n\log n)$ for $n\ge 2$. Additional sorting space depends on the selected sorting algorithm. Part (d) proves that the returned number of meetings is minimum.