Interval Scheduling

Job

A Job

J

is a half closed half open interval

[s_{J}, f_{J}) \subseteq ℝ

, we say that

s_{J}

is it's start time and

f_{J}

is it's finishing time.

Job Compatibility for Two Jobs

We say that two jobs

I, J

are comptible iff

I \cap J \neq \emptyset

Note that two jobs where the finish time of one equals the start time of the other are still compatible

Job Compatibility

Suppose that

𝒥

is a collection of jobs then we say that

𝒥

's jobs are compatible iff for any

I, J \in 𝒥

such that

I \neq J

they are compatible.

Interval Scheduling Problem

Suppose that

𝒥

is a collection of jobs, find the largest subset

𝒮 \subseteq 𝒥

such that

𝒮

's jobs are compatible.

When trying to solve a problem using a greedy approach one can usually consider a collection of finite natural orderings that a normal human may guess. For example, for the interval scheduling problem we could consider the following approaches. Where we start with some element, and then iteratively try to add new elements so long as the new element is compatible and using some heuristic.

Earliest Start Time
Earliest Finish Time
Shortest Interval
Fewest Conflicts

For earliest start time we can see that it does not work via this counter example

Shortest Interval Counter Example

TODO: Earliest finish time implementation

It turns out that adding valid jobs based on earliest finish time yields an optimal solution

Earliest Finish Time Adding Criterion

Suppose that EFT run on a set of jobs

J

and is paused during iteration. If it's solution thus far is

S = (s_{1}, s_{2}, \dots, s_{k})

, and there is at least one job in

a \in J ∖ S

, such that

S \cup {a}

is compatible, then after this iteration EFT will increase it's solution by exactly one job.

Earliest Finish Time is Optimal

Suppose that we are given jobs $J = (j_{1}, j_{2}, j_{3}, . . ., j_{w})$ EFT selects jobs $S : = (s_{1}, s_{2}, \dots s_{k})$ . Recall that an optimal solution is one that maximizes the number of scheduled jobs, suppose the optimal solutions all have length $m$ . Before continuing we should note that $k < m$ , this is because $S$ is not optimal

Let $opt (J)$ be the collection of optimal solutions (note that it is finite), and for each $O \in opt (J)$ , there is some $l \in [1 \dots k]$ such that for every $j \in [1 \dots l], s_{j} = o_{j}$ and $s_{l + 1} \neq o_{l + 1}$ , we will denote this value by $M_{O}$ . Note that this formalizes the idea of two tuples matching up to a certain index.

The above defines $f : opt (J) \to ℕ_{0}$ as $f (O) : = M_{O}$ . In english language, $f$ maps an optimal solution, to the index that it matches up to with respect to EFT's solution. Let $r : = \max (f (opt (J)))$ , then let $O^{⋆} \in f^{- 1} (r)$ be an optimal solution that matches with $S_{EFT}$ for the longest.

It's possible that $r = k$ , if that's true then we know that for every $i \in [1 \dots k], s_{i} = o_{i}$ . Let $m \geq j > k$ , then note that $o_{j}$ has the property that $S \cup {o_{j}}$ is compatible, therefore since $o_{j} \in J ∖ S$ , then by the lemma, EFT would have extended it's solution by one on the iteration after it added $s_{k}$ producing a solution on the next iteration of $S = (s_{1}, \dots, s_{k}, x)$ where $x \in J$ , but clearly now we have $S \neq S$ , which is a contradiction, thus we know $r \neq k$

We are sure that $k < r$ is not true because $S$ only has $k$ indices. So for sure $r < k$ , by the way $r$ was defined this means that for every $j \in [1 \dots r], s_{j} = o_{j}$ , but that $s_{r + 1} \neq o_{r + 1}$ . Note that since $s_{r + 1} \neq o_{r + 1}$ and ETF adds by earliest finishing time, we must have that $f_{s_{r + 1}} \leq f_{o_{r + 1}}$ , since that's true we know that ${s_{r + 1}, o_{r + 2}, \dots o_{m}}$ is compatible, therefore $(o_{1}, o_{2}, \dots, o_{r}, s_{r + 1}, \dots, o_{m})$ is an optimal solution that matches with $S$ for $r + 1$ indices. This is impossible, because the maximum number of indices an optimal solution could match was $r$ .

Our assumption was that ETF doesn't produce an optimal solution, and we obtained a contradiction.

Note that in the above proof it's important to realize that if $S$ was optimal then $k = m$ and $r = k$ , and then in the latter part of the proof we wouldn't be able to talk about $s_{r + 1}$ because it would be an invalid index.