= Solution
Sort once by nondecreasing end time, then retain the most recent meeting:
``
Meetings(intervals):
sort intervals by nondecreasing end
result = []
haveMeeting = false
for (s,e) in intervals:
if not haveMeeting or s > lastMeeting:
lastMeeting = e
append e to result
haveMeeting = true
return result
``
When an interval is inspected, $\texttt{lastMeeting}\leq e$ because of the sorted end order. Therefore the interval is already covered exactly when $s\leq\texttt{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 \b[$O(n\log(n+1))$ time], conventionally $O(n\log n)$ for $n\geq2$. Additional sorting space depends on the selected <sorting algorithm>. Part (d) proves that the returned number of meetings is minimum.
Back to article page
