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

A greedy algorithm commits to a locally best available choice and then continues on the remaining problem without revising earlier choices. Correctness requires proving that such choices can belong to an optimal solution; local attractiveness alone is insufficient.

Kruskal's algorithm processes the edges of an undirected weighted graph in nondecreasing weight order. It accepts the next edge exactly when its endpoints lie in different components of the currently chosen forest, thereby preserving the absence of a cycle. This is greedy because it always chooses a cheapest available edge compatible with the forest constraint and never retracts an accepted edge.

The Kruskal safe edge argument explains why the choice works: if a minimum spanning tree extending the current forest lacks the chosen edge, adding that edge creates a cycle; an edge on that cycle crossing the same component boundary can be removed without decreasing connectivity. Such a crossing edge cannot be lighter than the chosen eligible edge, so the exchange does not increase total weight. The new minimum spanning tree includes the greedy choice. For a disconnected graph the same construction yields a minimum spanning forest rather than a single spanning tree.

Four closed intervals suffice:No time belongs to three intervals, so the maximum number of attendees at one meeting is two. Strategy 1 is allowed to choose $t=5/2$, which meets $I_2$ and $I_3$. The remaining intervals $I_1$ and $I_4$ are disjoint, requiring two further meetings. This run therefore uses three meetings.

However, times $1$ and $4$ meet everyone: $1\in I_1\cap I_2$ and $4\in I_3\cap I_4$. One meeting is impossible because $I_1\cap I_4=\varnothing$. Thus the optimum is two, while strategy 1 can use three. The counterexample deliberately uses an allowed tie between maximum-attendance choices: the instruction to pick “any” such time would require every tie choice to be safe.

The earliest end is $1$, so strategy 2 first meets at $t_1=1$, removing $I_1$ and $I_2$. Among the remaining intervals the earliest end is $4$, so it next meets at $t_2=4$, removing $I_3$ and $I_4$. This is the two-meeting optimum proved in part (b). The closed endpoints are essential: attendance at exactly an interval's endpoint is permitted.

Let $I_i=[s_i,t_i]$ be an interval whose earliest end triggers greedy meeting $i$. After that meeting, every remaining interval starts strictly after $t_i$: its end is at least $t_i$, and otherwise it would contain $t_i$ and be removed. HenceThe witness intervals $I_1,\dots ,I_k$ are therefore pairwise disjoint. Every feasible schedule needs a distinct meeting in each one, yielding a lower bound of $k$. The greedy schedule uses exactly $k$ meetings and covers everyone, so it is optimal. This is an optimality certificate for the interval stabbing problem.

To follow the source's suggested contradiction explicitly, suppose a schedule $u_1<\cdots <u_j$ with $j<k$ covered everyone. Since $I_1$ ends at $t_1$, some $u_{\ell }\le t_1$, so $u_1\le t_1$. If $u_i\le t_i$ and $i<j$, then none of the first $i$ alternative meetings can hit $I_{i+1}$, which starts after $t_i$. A later meeting must hit it by its end $t_{i+1}$, implying $u_{i+1}\le t_{i+1}$. Mathematical induction gives $u_i\le t_i$ for $1\le i\le j$. But $I_{j+1}$ starts after $t_j\ge u_j$, later than every alternative meeting. It is uncovered, a contradiction. For $j=0$ a nonempty family is immediately uncovered. The source's hint starts at index zero without defining $u_0,t_0$; the proof above starts at the actual first meetings instead.

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.