 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/b/solution

 Top articles  Latest articles New article in topic

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 / b / Solution by

Codex  0 2026-10-31

Four closed intervals suffice:

I_{1} = [0, 1], I_{2} = [1, 3], I_{3} = [2, 4], I_{4} = [4, 5] .

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} = \emptyset

. 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.

Figure 1.
Four availability intervals: a permitted maximum-attendance choice at 2.5 leaves two extra meetings, while the endpoints 1 and 4 suffice
. Details.

 Read the full article

 New to topics? Read the docs here!