28 The Interval Scheduling problem

Setting

• We are given a 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 given 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 Interval Scheduling Problem

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

Failed Attempt 1

Always select the request which starts the earliest, i.e., one having minimum starting time.

Failed Attempt 2

Always select the request which needs minimum time to be handled, i.e., the request $\mathrm{Req}(i)$ which minimises $\mathrm{Finish}(i)-\mathrm{Start}(i)$

Failed Attempt 3

Always select the request which has fewest conflicting requests.

The correct greedy algorithm

$$\begin{array}{rl}1:& \text{Let }R=\{\text{Req}(1),\text{Req}(2),\dots ,\text{Req}(i),\dots ,\text{Req}(n)\}\text{ be set of all requests}\\ 2:& \text{Let }C\text{ denote set of requests that we select}\\ 3:& \text{Initiate }C=\{\varnothing \}\\ 4:& \text{while }R\ne \varnothing \text{ do}\\ 5:& \text{Find the request }\text{Req}(i)\in R\text{ which has smallest finish time}\\ 6:& \text{Add }\text{Req}(i)\text{ to }C\\ 7:& \text{Delete from }R\text{ all requests that conflict with }\text{Req}(i)\\ 8:& \text{end while}\end{array}$$

• Observation: $C$ does not contain any conflicting requests (from line 7)
• Suppose there is another algorithm ANY which selects strictly more requests that our greedy algorithm
• Let GREEDY selects $\mathrm{Req}(\mathrm{Greed}{\mathrm{y}}_1),\mathrm{Req}(\mathrm{Greed}{\mathrm{y}}_2),\cdots ,\mathrm{Req}(\mathrm{Greed}{\mathrm{y}}_{\mathrm{k}})$ in that order
• Let ANY schedule $\mathrm{Req}(\mathrm{AN}{\mathrm{Y}}_1),\mathrm{Req}(\mathrm{AN}{\mathrm{Y}}_2),\cdots ,\mathrm{Req}(\mathrm{AN}{\mathrm{Y}}_{\mathrm{m}})$ in that order for some $m>k$
• Lemma: For each $1\le l\le k$, we have $\mathrm{Finish}(\mathrm{GREED}{\mathrm{Y}}_{\mathrm{l}})\le \mathrm{Finish}(\mathrm{AN}{\mathrm{Y}}_{\mathrm{l}})$
  • Proof by induction on $l$. Base case is $l=1$
  • Inductive step: $\mathrm{START}(\mathrm{AN}{\mathrm{Y}}_{\mathrm{l}})\ge \mathrm{FINISH}(\mathrm{AN}{\mathrm{Y}}_{\mathrm{l}-1})\ge \mathrm{FINISH}(\mathrm{GREED}{\mathrm{Y}}_{\mathrm{l}-1})$
  • So, $\mathrm{Req}(\mathrm{AN}{\mathrm{Y}}_{\mathrm{l}})$ does not conflict with $\mathrm{Req}(\mathrm{GREED}{\mathrm{Y}}_{\mathrm{l}-1})$
  • But our algorithm choose $\mathrm{Req}(\mathrm{GREED}{\mathrm{Y}}_{\mathrm{l}})$ instead of $\mathrm{Req}(\mathrm{AN}{\mathrm{Y}}_{\mathrm{l}})$, i.e., $\mathrm{Finish}(\mathrm{GREED}{\mathrm{Y}}_{\mathrm{l}})\le \mathrm{Finish}(\mathrm{AN}{\mathrm{Y}}_{\mathrm{l}})$
• Since $m>k$, $\mathrm{ANY}$ selects a request $\mathrm{Req}(\mathrm{AN}{\mathrm{Y}}_{\mathrm{k}+1})$
  • $\mathrm{Start}(\mathrm{AN}{\mathrm{Y}}_{\mathrm{k}+1})\ge \mathrm{FINISH}(\mathrm{AN}{\mathrm{Y}}_{\mathrm{k}})\ge \mathrm{FINISH}(\mathrm{GREED}{\mathrm{Y}}_{\mathrm{k}})$
  • Contradiction to our algorithm stopping after selecting $\mathrm{Req}(\mathrm{GREED}{\mathrm{Y}}_{\mathrm{k}})$