Greedy — exchange argument proof technique: Worked examples

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

Tumne recipe parent note (3.7.3) mein dekhi hai. Yeh page drill hall hai: hum har tarah ki situation se guzarte hain jo ek exchange argument face kar sakta hai, taaki jab koi naya problem tumhare saamne aaye toh tum uski shape pehle se pehchaan lo.

Koi bhi symbol use hone se pehle, yeh hai woh notation jo poore page mein use hoti hai, simple words mein:

Definition Sequence notation

$g_{i}$ , $o_{i}$ , aur "inversion" ka matlab

$O$ = koi bhi optimal solution (best possible score achieve karta hai).
$G$ = woh solution jo greedy build karta hai.
Hum dono ko ordered lists ke roop mein likhte hain: $G = (g_{1}, g_{2}, \dots, g_{n})$ aur $O = (o_{1}, o_{2}, \dots, o_{n})$ . Yahan $g_{i}$ = greedy ka $i$ -th choice in order (toh $g_{1}$ greedy ki sabse pehli pick hai), aur $o_{i}$ = optimal solution $O$ ki position $i$ mein baitha element. Subscript sirf slot number hai, $1$ se count karte hue.
$O$ mein ek inversion positions $i < j$ ka ek aisa pair hai jahan $o_{i}$ aur $o_{j}$ greedy ki sorting rule ke ulte order mein hain — yaani greedy ki key kehti hai $o_{j}$ ko $o_{i}$ se pehle aana chahiye, phir bhi $O$ mein $o_{i}$ pehle hai. Adjacent inversion special case hai $j = i + 1$ (dono offending elements neighbours hain). Ek dhundhne ke liye: $O$ ko left se right scan karo aur pehli position $i$ par ruko jahan $o_{i}$ ki key $o_{i + 1}$ ki key se "baad" ho.

Recall Do facts jo hum har jagah reuse karte hain (recap kiya gaya taaki yeh page akele kaam kare)

Completion time. Agar jobs ek ek karke run hoti hain, toh kisi job ki finish time $C_{k}$ = uski start plus uske aane tak run ki gayi har cheez ki total length, khud usse including. Unweighted total completion time hai $\sum_{k} C_{k}$ .
$\sum C_{k}$ ke liye adjacent-swap identity. Maano do adjacent jobs $a$ (pehle) phir $b$ time $t$ par start karti hain. Tab $C_{a} = t + p_{a}$ aur $C_{b} = t + p_{a} + p_{b}$ hai, toh unka combined contribution hai $(t + p_{a}) + (t + p_{a} + p_{b}) = 2 t + 2 p_{a} + p_{b}$ . Unhe swap karo aur yeh $2 t + 2 p_{b} + p_{a}$ ban jaata hai. Poore schedule cost mein sirf in do terms mein change hota hai, toh $Δ = cost (O) - cost (O^{'})$ ke saath swap ka difference hai $(2 p_{a} + p_{b}) - (2 p_{b} + p_{a}) = p_{a} - p_{b}$ . Shorter se pehle Longer rakhna cost mein exactly $p_{a} - p_{b}$ zyada deta hai.

Scenario matrix

Neeche har cell ek distinct behaviour hai jo ek exchange swap dikha sakta hai. Cell column ek letter ID ( $A$ – $I$ ) hai jise hum "cell A", "cell B", etc. kehte hain; har worked example un cells ke saath tagged hai jo woh cover karta hai.

Cell	Scenario class	Swap cost ke saath kya karta hai	Example
A	Strict improvement (minimisation)	$Δ > 0$ : cost strictly drop hoti hai → contradiction	Ex 1
B	Equal cost (counting / maximisation)	$Δ = 0$ : cost unchanged → still optimal	Ex 2
C	Ratio / weighted objective	$Δ$ ka sign ek ratio rule se tay hota hai	Ex 3
D	Two-swap construction	dono terms sum karne zaroori hain	Ex 4
E	Degenerate input (ties, equal keys)	$Δ = 0$ , greedy phir bhi theek	Ex 5
F	Zero / empty / single element	base case, koi swap possible nahi	Ex 6
G	Jahan greedy FAIL karta hai (koi exchange lemma nahi)	swap cost increase kar sakta hai ( $Δ < 0$ )	Ex 7
H	Real-world word problem	A ya C mein translate karo	Ex 8
I	Exam twist (non-adjacent swap, chain prove karo)	door items swap karo	Ex 9

Prerequisites jo tumhare paas open hone chahiye: Proof by contradiction, Induction, Greedy Algorithms — general paradigm.

Example 1 — Strict improvement (cell A)

Worked example SPT mein adjacent inversion, numbers ke saath

Statement. Do jobs, lengths $p_{a} = 7$ , $p_{b} = 3$ , dono time $t = 4$ par start karte hain. Ek optimal-lagging schedule long job $a$ pehle run karta hai. Dikhao ki swap karne se strictly smaller total completion time $\sum C_{k}$ milti hai, aur kitna.

Forecast: guess karo — kya total drop karega, aur kya drop $7 - 3$ ke barabar hoga?

"Long-first" order compute karo. $C_{a} = t + p_{a} = 4 + 7 = 11$ . Phir $C_{b} = t + p_{a} + p_{b} = 4 + 7 + 3 = 14$ . Sum $= 25$ . Yeh woh order hai jisme adjacent inversion hai: positions $i = 1, j = 2$ mein $o_{1} = a$ (long) $o_{2} = b$ (short) se pehle hai, SPT ke "short first" ke ulta. Yeh step kyun? Kisi job ki finish time uski start plus usse include karke sab kuch run hone ka sum hai; doosri job pehli ka wait karti hai.
"Short-first" order $O^{'}$ compute karo. $C_{b} = t + p_{b} = 4 + 3 = 7$ . Phir $C_{a} = 4 + 3 + 7 = 14$ . Sum $= 21$ . Yeh step kyun? Swapping sirf pair ko reorder karta hai; pair ke bahar ki jobs untouched rehti hain, toh sirf yeh do terms move karti hain.
Difference. $Δ = cost (O) - cost (O^{'}) = 25 - 21 = 4 = p_{a} - p_{b}$ . Yeh step kyun? Recapped adjacent-swap identity use karte hue, do orders ka contribution hai $2 t + 2 p_{a} + p_{b}$ (long first) vs $2 t + 2 p_{b} + p_{a}$ (short first). $2 t$ cancel ho jaata hai, gap $(2 p_{a} + p_{b}) - (2 p_{b} + p_{a}) = p_{a} - p_{b}$ reh jaata hai — jo job doosre number par finish hoti hai woh doosri ki length pay karti hai, toh shorter job pehle rakhna doubled term ko chhota karta hai.

Verify: $p_{a} - p_{b} = 7 - 3 = 4$ . ✅ Direct sum $25 - 21$ se match karta hai. Units: time-units; shorter-first order 4 time-units ka wait bachata hai. Kyunki $Δ > 0$ strictly hai, "long-first" optimal nahi ho sakta — cell A.

Example 2 — Equal cost (cell B)

Worked example Activity selection: pehli pick swap karo, count barabar rehta hai

Statement. Activities (start, finish): $A = [1, 4)$ , $B = [3, 5)$ , $C = [0, 6)$ , $D = [5, 7)$ , $E = [6, 8)$ . Maximum number of non-overlapping intervals pick karo. Greedy ki pehli pick ke saath exchange test karo.

Forecast: greedy earliest-finishing activity pick karta hai. Woh kaun hai, aur kya ek optimal pick ko isse replace karne se count same rahega?

Neeche ki figure sab paanch intervals ko time axis par horizontal bars ke roop mein draw karti hai; swap dekhne ke liye iska use karo.

Figure (alt-text). Time axis (0 se 8) par paanch horizontal bars. Bar $A$ time 1–4 tak span karta hai (orange), $B$ 3–5 tak (plum), $C$ 0–6 tak (grey), $D$ 5–7 tak (teal), $E$ 6–8 tak (grey). Time 4 par ek orange dashed vertical line mark karta hai jahan $A$ finish hota hai; ek label note karta hai ki $D$ 5 par start hota hai, toh $D$ $A$ ke baad bhi fit hota hai. Ek orange arrow $A$ ki taraf point karta hai ("greedy g1 = earliest finish 4") aur ek plum arrow swap $B \to A$ dikhata hai count 2 par same rakhte hue.

Notation yaad karo: $g_{1}$ = greedy ki pehli choice, aur $o_{1}$ = optimal list $O$ ki position 1 mein element (yahan $O$ finish-time order mein likha gaya hai).

Greedy ki pehli pick $g_{1}$ dhundho. Finish times: $A : 4, B : 5, C : 6, D : 7, E : 8$ . Earliest finish $A$ hai (finish $4$ ). Toh $g_{1} = A$ — figure mein orange bar. Yeh step kyun? Activity Selection Problem ke liye greedy ka rule hai "compatible mein se earliest finish."
Ek optimal solution lo. Maximum non-overlapping count yahan $2$ hai, e.g. $O = {A, D}$ ya $O = {B, D}$ ya $O = {B, E}$ . $O = (B, D)$ lo (jisme $A$ nahi hai), toh $o_{1} = B$ , $o_{2} = D$ . Yeh step kyun? Hume ek aisa optimal $O$ chahiye jo pehli pick par greedy se disagree kare, swap demonstrate karne ke liye.
$o_{1} = B$ ko $g_{1} = A$ se swap karo. Figure mein, $A$ finish hota hai $4 \leq 5 =$ finish of $B$ par. Agli chosen activity $D = [5, 7)$ start hoti hai $5 > 4$ par (dashed line ke right mein), toh woh abhi bhi compatible hai. Naya set $O^{'} = (A, D)$ , size $2$ . Yeh step kyun? $g_{1}$ ka finish $o_{1}$ se no later hai, toh jo bhi $o_{1}$ ke baad fit hota tha woh $g_{1}$ ke baad bhi fit hoga — feasibility preserved. (Ek exchange proof ki hamesha do obligations hoti hain: result abhi bhi legal hai aur no worse hai.)

Verify: $∣ O^{'} ∣ = 2 = ∣ O ∣$ , toh $Δ = cost (O) - cost (O^{'}) = 0$ . ✅ Same count — ek maximisation/counting problem $Δ = 0$ deta hai (cell B), aur $O^{'}$ ab pick 1 par greedy se agree karta hai. Sanity check: ${A, D}$ mein koi do intervals overlap nahi karte kyunki $4 \leq 5$ hai (dashed line ke paas koi bar-overlap visible nahi hai).

Example 3 — Ratio / weighted objective (cell C)

Worked example Smith's rule decide karta hai kaun pehle jaata hai

Statement. Do jobs, $(p_{a}, w_{a}) = (6, 2)$ aur $(p_{b}, w_{b}) = (2, 3)$ , weighted objective $\sum w_{k} C_{k}$ , dono $t = 0$ par start karte hain. Kaun sa order optimal hai, aur ek adjacent swap ka cost change kya hai?

Forecast: SPT kehta hai "shorter first" ⇒ $b$ pehle (length 2). Par weights matter karte hain — guess karo kya ratio $p / w$ agree karta hai.

Woh rule recap karte hain jis par hum lean karte hain: weighted completion time $\sum w_{k} C_{k}$ ke liye, $a$ (pehle) phir $b$ ka adjacent swap cost mein $w_{b} p_{a} - w_{a} p_{b}$ change karta hai. Yeh non-negative hota hai exactly jab $p_{a} / w_{a} \geq p_{b} / w_{b}$ , toh correct greedy ratio $p_{k} / w_{k}$ se sort karta hai (Smith's rule — weighted completion time), sirf length se nahi. (Unweighted $\sum C_{k}$ special case hai $w_{k} = 1$ ke saath, SPT recover karta hai.)

Ratios $p / w$ compute karo. Job $a$ : $6/2 = 3$ . Job $b$ : $2/3 \approx 0.667$ . Smaller ratio pehle ⇒ $b$ before $a$ . Yeh step kyun? Recapped rule se, $a$ ko $b$ se pehle order karna galat hai exactly jab $p_{a} / w_{a} \geq p_{b} / w_{b}$ ho, jo yahan hold karta hai ( $3 \geq 0.667$ ).
$a$ first ke saath cost. $C_{a} = 6$ , $C_{b} = 6 + 2 = 8$ . Cost $= w_{a} C_{a} + w_{b} C_{b} = 2 \cdot 6 + 3 \cdot 8 = 12 + 24 = 36$ . Yeh step kyun? "Wrong" order ke liye objective ka direct evaluation (inversion, kyunki $a$ ka ratio $\geq$ $b$ ka hai).
$b$ first ke saath cost. $C_{b} = 2$ , $C_{a} = 2 + 6 = 8$ . Cost $= w_{b} C_{b} + w_{a} C_{a} = 3 \cdot 2 + 2 \cdot 8 = 6 + 16 = 22$ . Yeh step kyun? Woh order jo Smith's rule recommend karta hai.
Swap formula check. Yahan $O$ = ( $a$ first), $O^{'}$ = ( $b$ first). General adjacent-swap change hai $cost (O) - cost (O^{'}) = w_{b} p_{a} - w_{a} p_{b} = 3 \cdot 6 - 2 \cdot 2 = 18 - 4 = 14$ . Yeh step kyun? Yeh general expression $36 - 22$ ke barabar hona chahiye.

Verify: $Δ = 36 - 22 = 14 = w_{b} p_{a} - w_{a} p_{b}$ . ✅ Ratio comparison: $3 > 0.667$ , toh $a$ -first worse hai, $Δ > 0$ se confirm hota hai. Cell C — $Δ$ ka sign ek ratio se govern hota hai, raw length se nahi.

Example 4 — Two-swap construction (cell D)

Worked example Huffman sibling lemma real frequencies ke saath

Statement. Symbol frequencies $f (x) = 1$ , $f (y) = 2$ (do sabse chhote). Kisi optimal tree mein deepest sibling leaves $a, b$ hain with $f (a) = 4$ , $f (b) = 5$ , depths $d_{a} = d_{b} = 3$ par, jabki $x, y$ depths $d_{x} = 1$ , $d_{y} = 2$ par baithe hain. Dikhao ki double swap cost increase nahi karta.

Recap: ek prefix code ki cost hai $\sum_{c} f (c) depth (c)$ (har symbol apni frequency times kitne bits uska codeword use karta hai pay karta hai). Do leaves ki positions swap karna har frequency ko doosre ki depth par move karta hai; ek swap $u \leftrightarrow v$ ka cost change algebraically $(f (v) - f (u)) (d_{u} - d_{v})$ mein collapse ho jaata hai.

Sign note. Yahan $Δ = cost (O^{'}) - cost (O)$ track karna (new minus old — page ke baaki hisse ke reverse mein) sabse clean hai, kyunki classic lemma $Δ \leq 0$ dikhana chahta hai. Hum ise flag karte hain taaki direction kabhi surprise na kare.

Forecast: do alag swaps hote hain. Guess karo — kya dono cost changes ka sum $\leq 0$ hai?

Pehla swap $x \leftrightarrow a$ . Change $= (f (a) - f (x)) (d_{x} - d_{a}) = (4 - 1) (1 - 3) = 3 \cdot (- 2) = - 6$ . Yeh step kyun? $u = x, v = a$ ke saath recapped one-swap identity apply karo.
Doosra swap $y \leftrightarrow b$ . Change $= (f (b) - f (y)) (d_{y} - d_{b}) = (5 - 2) (2 - 3) = 3 \cdot (- 1) = - 3$ . Yeh step kyun? Huffman Coding ke sibling lemma ki construction do swaps karti hai; dono account karne zaroori hain, sirf ek nahi.
Total. $Δ = - 6 + (- 3) = - 9 \leq 0$ . Yeh step kyun? Har factor pattern hai (non-neg frequency gap) $\times$ (non-pos depth gap, kyunki $a, b$ deepest hain) $\leq 0$ ; summing karne par bhi $\leq 0$ rehta hai.

Verify: $Δ = - 9 < 0$ . ✅ Cost strictly drop hoti hai yahan, toh $x, y$ ko deepest sibling slot par push karna kabhi hurt nahi karta — sibling lemma hold karta hai. Agar hum sirf step 1 ( $- 6$ ) count karte toh hum improvement ko understate karte.

Example 5 — Degenerate input: ties (cell E)

Worked example Equal processing times,

$Δ = 0$ Statement. Do jobs, dono length $p_{a} = p_{b} = 5$ , $t = 0$ par start, unweighted $\sum C_{k}$ . Kya order matter karta hai?

Forecast: equal lengths ke saath, cost difference guess karo.

Order $a$ phir $b$ . $C_{a} = 5$ , $C_{b} = 10$ . Sum $= 15$ . Yeh step kyun? Standard completion-time evaluation.
Order $b$ phir $a$ . $C_{b} = 5$ , $C_{a} = 10$ . Sum $= 15$ . Yeh step kyun? Step 1 ke symmetric.
Difference. $Δ = cost (O) - cost (O^{'}) = p_{a} - p_{b} = 5 - 5 = 0$ . Yeh step kyun? Strict-improvement identity ( $Δ = p_{a} - p_{b}$ , top par recapped) ek equality ban jaati hai jab keys tie karte hain.

Verify: $15 - 15 = 0 = p_{a} - p_{b}$ . ✅ Cell E — ties $Δ = 0$ dete hain, toh koi bhi tie-breaking order optimal hai. Isi liye greedy proofs kehti hain "key se sort karo, ties arbitrarily break karo": exchange argument phir bhi $\geq$ ke saath chalta hai (strict $>$ kabhi zaroorat nahi).

Example 6 — Zero / single element (cell F)

Worked example Woh base case jisme koi swap nahi chahiye

Statement. (a) Ek empty job list. (b) Length $p_{1} = 9$ ki ek single job. Confirm karo ki greedy trivially optimal hai aur samjhao ki exchange induction yahan kyun bottom out karta hai.

Forecast: size $0$ ya $1$ ki list par kitne swaps possible hain?

Empty list. Total completion time $= \sum_{k} C_{k}$ zero jobs par $= 0$ . Invert karne ke liye koi pair nahi hai. Yeh step kyun? Exchange argument ke Induction ko base case chahiye; empty schedule vacuously optimal hai kyunki sirf ek hi solution hai.
Single job. Sirf order $[9]$ hai, $C_{1} = 9$ deta hai, total $= 9$ . Koi index $j > i$ exist nahi karta, toh " $O$ mein baad mein twin dhundho" ke paas swap karne ke liye kuch nahi. Yeh step kyun? "First difference" index $i$ ( $g_{i} \neq = o_{i}$ wala pehla slot) sirf tabhi find ho sakta hai jab do distinct orderings exist karein; ek element ke saath $G = O$ already hai.

Verify: empty cost $= 0$ ; single cost $= 9$ . ✅ Cell F — yeh induction base cases hain; har bada proof inhi tak reduce ho jaata hai.

Example 7 — Jahan greedy FAIL karta hai (cell G)

Worked example Koi exchange lemma exist nahi karta: coin change

${1, 3, 4}$ making 6 Statement. Denominations ${1, 3, 4}$ , amount $6$ fewest coins se banao. Dikhao ki greedy (largest coin $\leq$ remaining lo) beat ho jaata hai, toh koi exchange lemma hold nahi kar sakta.

Forecast: greedy pehle $4$ grab karta hai. Uska coin count true optimum se guess karo.

Greedy run karo. $6 \to$ $4$ lo (remainder $2$ ) $\to$ $1$ lo (remainder $1$ ) $\to$ $1$ lo (remainder $0$ ). Coins used: $4 + 1 + 1$ , count $= 3$ . Yeh step kyun? Yeh local "largest first" rule hai — locally best globally best nahi hota hamesha.
True optimum dhundho. $3 + 3 = 6$ , count $= 2$ . Yeh step kyun? Hum better solution exhibit karte hain prove karne ke liye ki greedy optimal nahi hai.
Koi exchange proof kyun exist nahi karta. Ek exchange lemma require karta: greedy ke $4$ se ek optimal coin replace karna count kabhi increase nahi karta. Par $3 + 3$ ke coins ko $4$ ki taraf swap karne se do $1$ 's force hote hain, count $2 \to 3$ raise karta hai — swap use worse banata hai ( $Δ = cost (O) - cost (O^{'}) = 2 - 3 = - 1 < 0$ ). Yeh step kyun? Cell G negative case hai: jab $Δ < 0$ possible ho, greedy sirf ek heuristic hai aur tumhe Dynamic Programming chahiye.

Verify: greedy count $= 3$ , optimal count $= 2$ , aur $3 > 2$ . ✅ Greedy strictly lose karta hai, toh ise exchange se certify karna impossible hai — matroid structures se contrast karo jahan Matroids and the greedy theorem exchange property guarantee karta hai.

Example 8 — Real-world word problem (cell H)

Worked example Photocopier queue — total wait minimise karo

Statement. Ek photocopier par chalon ki queue hai job times (minutes) $8, 2, 5, 3$ ke saath. Unhe order karo taaki sum of everyone's finish times (total waiting) minimise ho. Kaun sa order, aur total kya hai?

Forecast: kaun sa person pehle jaana chahiye? Ordering guess karo, phir total.

Translate karo. "Sum of finish times" $= \sum C_{k}$ , unweighted — yeh Ex 1 ki duniya hai. Greedy = Shortest Processing Time first (SPT). Yeh step kyun? Scheduling to minimise completion time ek word problem ko SPT model mein map karta hai, toh cell H, cell A mein reduce ho jaata hai.
Ascending sort karo. $2, 3, 5, 8$ . Kisi bhi starting order mein jahan longer job shorter se pehle ho ek inversion hai; cell-A argument har ek ko $p_{long} - p_{short}$ ke strict gain ke saath remove karta hai, toh optimum fully sorted hai. Yeh step kyun? Exchange argument (cell A) ne prove kiya ki koi bhi inversion strictly better ke liye remove ki ja sakti hai, toh optimum mein koi inversion nahi — woh sorted hai.
Sorted order ki finish times compute karo. $C_{1} = 2$ ; $C_{2} = 2 + 3 = 5$ ; $C_{3} = 5 + 5 = 10$ ; $C_{4} = 10 + 8 = 18$ . Total $= 2 + 5 + 10 + 18 = 35$ . Yeh step kyun? Har finish time saare earlier job lengths accumulate karta hai.
Ek bad order compare karo (e.g. $8, 5, 3, 2$ ): $8, 13, 16, 18$ , total $= 55$ . Yeh step kyun? Confirm karta hai ki sorted order genuinely better hai, aur gap $55 - 35 = 20$ saare inversion-removal gains ka total hai.

Verify: SPT total $= 35$ ; $8$ -first order $55$ deta hai, aur $35 < 55$ . ✅ Units: cumulative waiting ke minutes. Sorting ne $20$ person-minutes bachaye. Cell H closed — real words, cell-A machinery.

Example 9 — Exam twist: non-adjacent swap (cell I)

Worked example Door job ko forward bubble karo — poori chain prove karo

Statement. Schedule $O = (a, x, b)$ lengths $[p_{a}, p_{x}, p_{b}] = [9, 4, 2]$ ke saath $t = 0$ par start, unweighted $\sum C_{k}$ . Greedy ki pehli pick length- $2$ job $b$ hai (SPT), yaani $g_{1} = b$ , lekin $O$ mein woh position $3$ par baitha hai ( $o_{3} = b$ ) — front se non-adjacent. Dikhao ki jab $b$ front par move hota hai toh total drop hota hai, aur yeh total gain adjacent-swap gains ke sum ke barabar hai — toh ek far swap sach mein "no worse" steps ki ek chain hai.

Forecast: $b$ ko do positions forward move karna do adjacent swaps hain. Guess karo kya total gain har swap ke gain ke sum ke barabar hai.

Pehla difference dhundho. Greedy ki pehli pick $g_{1} = b$ hai, lekin $o_{1} = a \neq = b$ hai, toh pehla disagreeing slot $i = 1$ hai. Hume is pehle difference par swap karna chahiye (arbitrary ek par nahi) taaki induction $G$ ki taraf march kare. Yeh step kyun? Pehle difference par swap karna hi termination guarantee karta hai — swap ke baad, position $1$ greedy se match karta hai aur matched rehta hai.
Original order $O = (a, x, b)$ . $C_{a} = 9$ , $C_{x} = 9 + 4 = 13$ , $C_{b} = 13 + 2 = 15$ . Total $= 9 + 13 + 15 = 37$ . Hum sirf adjacent swaps directly justify kar sakte hain, toh $b$ ko ek ek neighbour forward bubble karte hain instead of teleport karne ke. Yeh step kyun? Adjacent-swap identity sirf neighbours par apply hoti hai; ek far move decompose karna zaroori hai.
$x \leftrightarrow b$ swap karo (pehla adjacent swap). Naya order $(a, b, x)$ . Recapped identity se, "longer $x$ before shorter $b$ " ka adjacent swap gain karta hai $Δ_{1} = p_{x} - p_{b} = 4 - 2 = 2$ . Naya total $= 37 - 2 = 35$ . Check: $C_{a} = 9, C_{b} = 9 + 2 = 11, C_{x} = 11 + 4 = 15$ , sum $= 35$ . ✅ Yeh step kyun? $b$ aur $x$ yahan adjacent hain, toh identity apply hoti hai aur swap "no worse" hai (yahan strictly better).
$a \leftrightarrow b$ swap karo (doosra adjacent swap). Naya order $(b, a, x)$ . "Longer $a$ before shorter $b$ " ka adjacent swap gain karta hai $Δ_{2} = p_{a} - p_{b} = 9 - 2 = 7$ . Naya total $= 35 - 7 = 28$ . Check: $C_{b} = 2, C_{a} = 2 + 9 = 11, C_{x} = 11 + 4 = 15$ , sum $= 28$ . ✅ Yeh step kyun? $b$ ab front tak pahunch gaya hai, toh schedule finally greedy ki pehli pick se agree karta hai — induction tail $(a, x)$ par proceed karta hai.
Chain assemble karo. Humne banaya $O = O_{0} = (a, x, b) \to O_{1} = (a, b, x) \to O_{2} = (b, a, x)$ ( $G$ se pick 1 par agree karta hai), cost ke saath: $37 \geq 35 \geq 28$ . Total gain $cost (O_{0}) - cost (O_{2}) = 37 - 28 = 9$ aur do adjacent gains sum karte hain $Δ_{1} + Δ_{2} = 2 + 7 = 9$ . Yeh step kyun? Yeh exchange argument ka telescoping heart hai: ek non-adjacent move ek chain of adjacent swaps mein decompose hota hai, har ek individually justified, toh $cost (O) \geq cost (O_{1}) \geq \dots \geq cost (G)$ kabhi rise nahi karta.

Conclusion. Kyunki har step "no worse" tha (yahan strictly better) aur hum pehli job par greedy se agree karte hue finish kiye, wahi reasoning recursively tail par apply hone se $O$ poori tarah $G$ mein transform ho jaata hai bina cost kabhi increase kiye. Isliye greedy (SPT) optimal hai — cell I closed.

Verify: $37 - 28 = 9$ aur do adjacent gains sum karte hain $2 + 7 = 9$ . ✅ Cell I — ek far swap adjacent swaps ki chain hai, telescoping inequality se match karta hai.

Recall

Recall Cell ko behaviour se match karo

Kis cell mein $Δ = 0$ (equal cost) hai kyunki woh objects count karta hai? ::: Cell B (activity selection, maximisation). Cell C mein, kaun si quantity decide karti hai kaun pehle jaata hai? ::: Ratio $p_{k} / w_{k}$ (Smith's rule), raw length nahi. Cell G (coins ${1, 3, 4}$ , amount 6) koi exchange proof admit kyun nahi karta? ::: Greedy ke coin ki taraf ek swap count increase kar sakta hai ( $2 \to 3$ ), toh "swap ke baad no worse" false hai ( $Δ < 0$ ). Ek non-adjacent swap (cell I) ko kaise justify kiya jaata hai? ::: Adjacent swaps ki ek chain ke roop mein, har ek apni khud ki "no worse" inequality ke saath; gains sum hote hain. $g_{i}$ ka kya matlab hai, $o_{i}$ se alag? ::: $g_{i}$ = greedy ka $i$ -th choice in order; $o_{i}$ = optimal list $O$ ki position $i$ mein element.