$(2$ points$)$ Recall the Interval Scheduling Problem: We are given as input a set of $n$ requests $($e$.$g$.,$ for

the use of an auditorium$),$ with a known start time $s_i$ and finish time $f_i$ for each request $i.$ Two requests

conflict if they overlap in time $-$ if one of them starts strictly between the start and finish times of the

other. Our goal is to select a maximum$-$cardinality subset of the given requests that contains no conflicts.

We discussed a greedy algorithm for this problem with the following structure: at each iteration we sclect.

a new request $i,$ including it in the solution$-$so$-$far and deleting from future consideration all requests

that conflict with $i.$ Which of the following greedy rules is guaranteed to always compute an optimal

solution?

A$.$ At each iteration, pick the remaining request which requires the least time $($i$.$e$.,$ has the smallest

value of $f_i-s_i),$ breaking ties arbitrarily.

B$.$ At each iteration, pick the remaining request with the earliest start time $($breaking ties arbi$-$

trarily$).$

C$.$ At each iteration, pick the remaining request with the earliest finish time, breaking ties arbi$-$

trarily.

D$.$ At each iteration, pick the remaining request with the fewest number of conflicts with other

remaining requests $($breaking ties arbitrarily$).$

For each of the greedy rules that you did not select for Interval Scheduling above, give an input instance

on which it fails, thereby proving that it is not correct. Give each instance in the boxes provided, using

an illustration of the requests, showing$/$saying what the optimal solution is$,$ as well as the incorrect

greedy solution. Please strive to depict the simplest$/$smallest counterexample you can find.

$($a$)(4$ points$)$ Choose which of the above greedy rules you are giving a counterexample for:$A,B,C,D$

b$)4$ points$)$ Choose which of the above greedy rules you are giving a counterexample for: $$A$,$B$,$C$,$D

c$)4$ points$)$ Choose which of the above greedy rules you are giving a counterexample for: $$A$,$B$,$C$,$D