Greedy — exchange argument proof technique: Visual walkthrough

3.7.3 · D2 · Coding › Algorithm Paradigms › Greedy — exchange argument proof technique

Hum ek sentence prove karne wale hain:

Woh greedy schedule jo sabse chhota job pehle chalata hai, total finishing time ko minimise karta hai.

End tak tum ise dekhoge, sirf believe nahi karoge.

Step 0 — Kisi bhi symbol se pehle ke words

Ek single machine imagine karo — maano ek microwave. Ek waqt mein sirf ek job chal sakta hai. Har job ki ek length hoti hai (usse kitne seconds chahiye). Hum jobs ko ek queue mein line up karte hain aur unhe ek ke baad ek chalate hain, koi gap nahi.

"Length" aur "completion time" mein jo farq hai wahi poori story hai, isliye ise pakad ke rakho: ek 2-second job jo time 5 par start hoti hai uski length 2 hai lekin completion time 7 hai.

Humara goal — woh cheez jo hum jitna chhota ho sake chahte hain — har job ke finishing moment ka sum hai:

$total = \sum_{k} C_{k} saare jobs par add karo k \sum job k kab khatam hoti hai C_{k}$

Figure — Greedy — exchange argument proof technique

Step 1 — Kyun ek job ka ending time ek running total hai

KYA. Timeline par teen jobs dekho. Pehle job ka finish sirf uski apni length hai. Doosre job ka finish pehli length plus uski apni hai. Teesra pehle dono ke liye pay karta hai plus apne liye.

KYUN. Kyunki koi gap nahi hai: har job exactly wahan start hoti hai jahan pichli khatam hui thi. Toh ek completion time ek prefix sum hai — yeh apne pehle sab jo bhi chala usse drag karta hai.

PICTURE. Figure mein coral brackets follow karo: har finishing moment pehle saari lengths ke upar wapas pahunchti hai.

$C_{(1)} = p_{(1)}, C_{(2)} = p_{(1)} + p_{(2)}, C_{(3)} = p_{(1)} + p_{(2)} + p_{(3)}$

Yahan $p_{(1)}$ ka matlab hai "jo bhi job hum pehle chalane ke liye choose karte hain uski length", wagairah — parentheses queue mein position batate hain, job ka naam nahi.

Step 2 — Dushman ka naam rakho: ek inversion

SPT (shortest-processing-time first) ko best sabit karne ke liye, hum ise ek saath saare schedules ke against compare nahi karte. Iske bajaye hum ek chhoti si local defect dhundh ke use kuchal dete hain.

KYUN yeh dushman hai. SPT ka matlab hai "shortest first" — jo exactly "koi longer-before-shorter neighbours nahi" hai. Toh ek schedule greedy wala hai agar aur sirf agar usmein zero inversions hain. Agar hum prove kar sakein ki har inversion ko bina total ko hurt kiye hataya ja sakta hai, toh hum ek solution ko saaf kar sakte hain jab tak woh greedy ban na jaaye.

PICTURE. Figure mein red pair ek inversion hai: tall coral block (long job $a$ ) short mint block (job $b$ ) ko block kar raha hai.

Step 3 — Swap, aur kyun sirf do numbers change hote hain

KYA. Inversion lo — neighbours $a$ phir $b$ — aur unhe swap karo: ab $b$ pehle chalta hai, phir $a$ . Baaki kuch nahi hilta.

KYUN sirf do numbers change hote hain. Pair se pehle schedule ki hui har cheez untouched hai, toh unki clocks identical hain. Pair ke baad ki har cheez bhi untouched hai — kyunki pair milke abhi bhi same total time $p_{a} + p_{b}$ occupy karta hai, toh baad ke jobs exactly same moment par start hote hain jaise pehle. Sirf $C_{a}$ aur $C_{b}$ differ kar sakte hain.

$t$ ko woh clock reading maano jis moment pair start hota hai (letter $t$ = "ab tak ka time, inme se koi ek run karne se pehle").

PICTURE. Figure mein grey region (pehle) aur striped region (baad) frozen hain; sirf do coloured blocks jagah badal rahe hain.

Swap se pehle (order $a$ phir $b$ ):

$C_{a} = t + p_{a}, C_{b} = t + p_{a} + p_{b}$

$C_{a} = t + p_{a}$ : job $a$ pair shuru hone ke $p_{a}$ seconds baad khatam hoti hai.
$C_{b} = t + p_{a} + p_{b}$ : job $b$ , $a$ ke peeche wait karta hai, toh yeh pehle $p_{a}$ pay karta hai phir apna $p_{b}$ .

Step 4 — Dono versions add karo aur subtract karo

KYA. Har order mein pair ka total mein contribution compute karo aur compare karo.

Order $a$ phir $b$ (the inversion):

$C_{a} + C_{b} = (t + p_{a}) + (t + p_{a} + p_{b}) = shared start 2 t + a do baar count hua 2 p_{a} + b ek baar p_{b}$

$p_{a}$ do baar kyun count hua? Kyunki job $a$ pehle chali, toh $a$ ki length dono completion times ke andar baithi hai.

Order $b$ phir $a$ (the fix):

$C_{b} + C_{a} = (t + p_{b}) + (t + p_{b} + p_{a}) = 2 t + 2 p_{b} + p_{a}$

KYUN. Jo bhi pehle jaata hai uski length double ho jaati hai. Toh doubled term ko chhota rakhne ke liye, hum chhota job pehle chahte hain.

PICTURE. Figure dono totals ko bar heights ke roop mein stack karta hai; farq ek single mint sliver hai.

Broken order mein se fixed order subtract karo:

$cost(inversion) - cost(fixed) = (2 p_{a} + p_{b}) - (2 p_{b} + p_{a}) = > 0 kyunki p_{a} > p_{b} p_{a} - p_{b}$

Step 5 — Ek swap se poore proof tak

KYA. Hum ne abhi dikhaya: koi bhi schedule jisme inversion hai optimal nahi hai, kyunki hum use strictly improve kar sakte hain.

KYUN yeh sab kuch finish kar deta hai. Maano optimal schedule $O$ mein ek inversion tha. Toh $Δ > 0$ hume ek strictly sasta schedule banane deta hai — contradiction, kyunki $O$ supposedly best tha. Toh optimal schedule mein koi inversion nahi hai. Lekin "no inversions" exactly greedy SPT order ki definition hai. Isliye SPT hi optimal hai. Yeh ek proof by contradiction hai jo swap par tika hua hai.

PICTURE. Chain: kisi bhi $O$ se start karo, inversions ek ek karke hatao (har arrow ek swap hai jo cost kabhi raise nahi karta), aur tum $G$ tak slide ho jaate ho, fully sorted greedy schedule.

$O = O_{0} \to O_{1} \to \dots \to O_{m} = G, cost (O_{i + 1}) \leq cost (O_{i})$

Step 6 — Degenerate aur edge cases (inhe kabhi skip mat karo)

Definition Woh cases jo hume check karne chahiye

Equal lengths $p_{a} = p_{b}$ : toh $Δ = p_{a} - p_{b} = 0$ . Swap kuch bhi nahi badalta — dono orders equally achhe hain. Greedy abhi bhi ek optimal order hai; bas unique nahi hai. Koi contradiction nahi, koi problem nahi.
Ek job ( $n = 1$ ): koi neighbours nahi, koi inversion possible nahi, greedy trivially optimal.
Zero-length job $p_{k} = 0$ : yeh apna $C_{k}$ add karta hai lekin kisi ko delay nahi karta. SPT ise pehle rakhta hai (shortest), jo sahi hai — ek instant job ko kisi ko kabhi block nahi karna chahiye.
Saari lengths equal: har order identical total deta hai; argument ka "no worse" (strictly better nahi) version abhi bhi hold karta hai — activity selection ke saath contrast dekho, jahan swap hamesha equal-cost hota hai.
Weighted version $\sum w_{k} C_{k}$ : swap ab $Δ = w_{b} p_{a} - w_{a} p_{b}$ deta hai, jo $\geq 0$ exactly tab hota hai jab $p_{a} / w_{a} \geq p_{b} / w_{b}$ — toh tumhe ratio $p_{k} / w_{k}$ se sort karna chahiye (Smith's rule), length se nahi. Har $w_{k} = 1$ set karne par hamaara plain SPT wapas milta hai.

Ek-picture summary

Upar ki saari cheez ek image mein compress ho jaati hai: ek broken schedule (ek inversion), swap arrow, aur woh strictly-shorter total bar jo yeh produce karta hai — chain ke saath neeche sorted greedy schedule tak slide karte hue.

Recall Feynman: poora walkthrough plain words mein

Imagine karo bachche ek microwave use kar rahe hain, aur hume sabke finishing times ka total add karke care hai. Jo job early chale wo peeche ke sab ko zyada wait karata hai, isliye uski length baar baar count hoti hai. Matlab shuruaat mein ek lamba job disaster hai. Ab maano tumne supposedly best line-up dhundha aur ek tall bachcha ek chhote bachche ke theek aage khada mila — unhe swap karo! Dono milke abhi bhi utna hi total time lete hain, toh baaki kisi ki clock nahi hilti. Lekin ab chhota bachcha jaldi khatam hota hai aur sirf chhoti length do baar count hoti hai lamba ki jagah — toh grand total gir jaata hai. Kyunki "best" line-up ko improve kiya ja sakta tha, woh sach mein best tha hi nahi. Sirf woh line-ups jinhe tum is tarah improve nahi kar sakte woh hain jinmein koi tall-before-short pair nahi — jo exactly "shortest first" hai. Toh shortest-first jeet jaata hai. Wahi single swap, baar baar repeat hota hai jab tak kuch fix karne ko nahi bchta, poora exchange argument hai.

Recall Self-check

$C_{k}$ kya measure karta hai — length ya finishing moment? ::: Finishing moment (wall-clock time jab job khatam hoti hai), jo uske including saari lengths ka prefix sum hai. Swap mein $2 t$ term kyun cancel ho jaata hai? ::: Dono orders pair ko same clock reading $t$ par start karte hain, toh shared-start contribution identical hai aur difference mein drop ho jaata hai. Unweighted swap ke liye $Δ$ kya hai, aur uska sign? ::: $Δ = p_{a} - p_{b}$ , strictly positive jab bhi $a$ (lamba) $b$ (chhota) se pehle aata hai, proving karta hai ki inversion beatable hai. Weighted case mein $Δ$ ki jagah kya aata hai? ::: $Δ = w_{b} p_{a} - w_{a} p_{b} \geq 0 ⟺ p_{a} / w_{a} \geq p_{b} / w_{b}$ , jo Smith's rule deta hai.

Connected notes: parent topic · Greedy Algorithms — general paradigm · Greedy-stays-ahead proof technique · Scheduling to minimise completion time · Smith's rule — weighted completion time · Activity Selection Problem · Huffman Coding · Proof by contradiction · Induction · Matroids and the greedy theorem · Dynamic Programming