 Solution

ID: 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/c/solution

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.

 New to topics? Read the docs here!