🏗️ $\Theta \rho ϵ\eta \Pi \alpha \tau \pi$🚧 (under construction)

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\left(J\right)$ be the collection of optimal solutions (note that it is finite), and for each $O\in opt\left(J\right)$, 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}\ne 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\left(J\right)\to {\mathbb{N}}_0$ as $f\left(O\right):=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\left(f(opt\left(J\right))\right)$, then let $O^{\star }\in f^{-1}\left(r\right)$ be an optimal solution that matches with $S_{\mathrm{E}\mathrm{F}\mathrm{T}}$ 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\ge j>k$, then note that $o_j$ has the property that $S\cup \left\{o_j\right\}$ 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\ne S$, which is a contradiction, thus we know $r\ne 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}\ne o_{r+1}$. Note that since $s_{r+1}\ne o_{r+1}$ and ETF adds by earliest finishing time, we must have that $f_{s_{r+1}}\le 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.