Okay let's continue the perfect 
correctness of our greedy algorithm for 
minimizing the sum of the weight of 
completion times and let's move onto 
understanding the ramifications of the 
exchange of jobs suggested at the 
conclusion of the previous video. 
So recall the basic ideas to use this 
observation that the optimal schedule 
sigma star by virtue of our assumption of 
being different from the greedy one has 
to have this pair of consecutive jobs 
where the earlier one has the higher 
index. 
So my question for you involves thinking 
about how the completion times of all of 
the jobs change after we make this 
exchange of the two jobs i and j. 
Which ones go up? 
Which ones go down? 
Which ones are unaffected? 
Which ones can we not actually predict 
whether they go up or down? 
All right, so the answer to this, quite 
key question is the third answer. Jobs 
other than I and J are unaffected, the 
completion time of job I goes up, and the 
completion time of job J goes down. 
So let's review why. Consider a job K, 
other than I or J, it's probably easiest 
to see if in sigma-star, K completes 
before I and J, scheduled earlier than I 
and J. 
Don't, remember what the completion time 
of a job is, it's just the time that 
needs to elapse before it gets done, so 
it's the sum of the job lengths up to, 
and including that job itself. 
So if K was scheduled before I and J 
before, it's exactly the same after I and 
J are swapped. 
You don't know the difference. 
Exactly the same set of jobs precedes Job 
K is the force whose completion time is 
the same. 
But if you think about it, this exact 
same argument is true for jobs K that 
succeed INJ. 
So before we do the swap, it has to wait 
for a bunches ops to complete, including 
INJ and after we swap INJ, it still has 
to wait for INJ to complete. 
Yeah, they complete in opposite order but 
who cares? 
The amount of time of the lapse is 
exactly the same. 
So importantly, jobs other than INJ are 
completely agnostic to the swap. 
Their completion time is exactly the same 
as before. 
So that's the first. 
Part. 
so job I, it's completion time goes up. 
It's easier to see why it used to be 
before J, now it has to wait for J. 
In fact we can say exactly how much 
completion time goes up by. 
It goes up by exactly the length of J. 
That is the extra time that now needs to 
elapse before I gets completed. 
By exactly the same reasoning the 
completion time of job j actually drops 
it has to wait for the same jobs to 
complete before it being accepted no 
longer has to wait for job I. 
So, not only can we say its completion 
time goes down we can say that it goes 
down so by precisely the length of job I. 
So now we are in a great position to 
finish off this proof. 
Let's summarize what we got so far. 
So, for a cost benefit analysis of 
exchanging I and J, we discovered the 
cost is limited to an increase in the 
completion time of job I and the benefit 
is limited to the decrease in the 
completion time of job J. 
Specifically the cost, the new cost 
incurred by the exchange is the weight of 
job I times the amount by which it's 
completion time went up, namely the 
length of job J. 
Similarly, the benefit of the exchange is 
the drop of LI and J's completion time 
and that gets multiplied by it's weight's 
of WJ. 
So now finally we are at the point where 
we can use the fact that this purportedly 
optimal schedule sigma star schedules I 
and J in some sense incorrectly, 
with a higher index job first despite it 
having a lower ratio in contrast to the 
principles followed by our greedy 
algorithm. 
So why is it relevant that the earlier 
job I has a higher index? 
Well, a higher index corresponds to a 
lower ratio. 
Remember we did this notation switch so 
that the first job has the highest ratio, 
the second job has the second highest 
ratio and so on. 
So the bigger your index, the further you 
are down in the ordering, the lower your 
ratio. 
So because I is bugger than J, that means 
I's ratio is worse than J. 
The usefulness of this becomes even more 
apparent when we clear denominators. 
We multiply both sides by the, by LI 
times LJ. 
And then we find that WI times LJ is 
strictly less than WJ times LI. 
But what are these, these are just the 
cost and benefit terms respectively of 
our thought experiment exchange, 
exchanging I and j. 
So what does it mean that the benefit of 
the swap outweighs the cost? 
It mean if we take sigma star, this 
reportedly optimal solution, and we 
invert the jobs I and j, we get a 
schedule with an even better weighted sum 
of completion times, but that is nuts. 
That's absurd, sigma star was supposed to 
be optimal. 
So here's our contradiction. 
That completes the proof.