32 Interval Scheduling problem (without weights)

Setting

• We are given set of $n$ requests $R=\{\mathrm{Req}(1),\mathrm{Req}(2),\cdots ,\mathrm{Req}(i),\cdots ,\mathrm{Req}(n)\}$
• $\{\mathrm{Req}(i)\}$ has a start time by $\mathrm{Start}(i)$ and a finish time given by $\mathrm{Finish}(i)$
• There is a machine which can handle one request at a time
• Two requests “conflict” if they overlap

The

Select a set $C\subseteq R$ of requests such that $|C|$ is maximised and no two requests from $C$ conflict.