Lesson 1 — Intermediate

Greedy: Intuition aur Proof

Greedy algorithm ek aisi technique hai jisme hum har step pe locally best choice lete hain aur ummeed karte hain ki wo globally bhi best ho. Aaj hum samjhenge greedy kab kaam karti hai aur kab nahi.

Greedy Algorithm Kya Hai?

Socho tum ek party mein ho aur tumhe limited dishes try karni hain. Tum har baar sabse tasty dish choose karte ho — yehi greedy approach hai. Tum locally best choice le rahe ho har baar.

Greedy algorithm mein hum ek array ya list ko process karte hain aur har step pe ek decision lete hain — bina Future ki tension liye. Yeh approach tab kaam karti hai jab problem mein do cheezein hoti hain:

• Greedy Choice Property — Jo locally optimal choice hai woh globally optimal solution ka part hai.
• Optimal Substructure — Problem ka optimal solution apne sub-problems ke optimal solutions se banta hai.

Example ke liye, agar tumhe minimum coins se amount banana hai aur coins hain [1, 5, 10, 25], toh greedy approach hai — har baar sabse bada coin lo jo fit ho. Yeh isliye kaam karta hai kyunki larger coins always efficient hain.

Greedy vs Dynamic Programming

Dono approaches optimal solutions deti hain, lekin fark hai:

• Greedy — Har step pe local best choice, bina backtrack kiye. O(n) ya O(n log n) mein chalta hai.
• DP — Har possible option consider karta hai, memoization ya tabulation use karta hai. Zyada time leta hai lekin guaranteed optimal.

Greedy tab kaam karta hai jab greedy choice property hold kare. Agar nahi karti, toh greedy wrong answer dega. Example: Coin change problem mein agar coins [1, 3, 4] hon aur amount 6 ho, greedy 4+1+1=3 coins dega lekin optimal 3+3=2 coins hai.

Proof by Exchange Argument

Greedy ka proof karne ka sabse common tarika hai exchange argument. Steps:

1. Maan lo optimal solution O hai aur greedy solution G hai.
2. Dikhao ki G mein pehla choice O ke pehle choice se better ya equal hai.
3. Agar O mein greedy choice nahi hai, toh usse exchange karo — solution worse nahi hoga.
4. Repeat karo jab tak O = G na ho jaye.

Activity Selection Problem mein yeh proof hota hai: Agar koi optimal solution pehle end hone wali activity select nahi karta, toh usse swap karo — overlap kam hoga ya same rahega.

Visual: Activity Selection

Neeche dekho kaise greedy approach kaam karta hai:

Activities (start, end):
 A: (1, 3) ——————
 B: (2, 5) ————————
 C: (4, 7) ————————
 D: (6, 9) ————————
 E: (8, 10) ——————

Greedy choice: Sort by END time ✓ Pick earliest ending first

Step 1: Pick A (1,3) ✓ end=3
Step 2: B starts at 2 < 3 ✓ SKIP
Step 3: C starts at 4 = 3 ✓ PICK, end=7
Step 4: D starts at 6 < 7 ✓ SKIP
Step 5: E starts at 8 = 7 ✓ PICK, end=10

Result: [A, C, E] — Maximum 3 activities!

Agar hum start time ke hisaab se sort karte aur pehla pick karte, toh shayad sirf 1-2 activities hoti. End time sort karne se zyada activities fit hoti hain — yeh greedy choice property ka example hai.

Code: Activity Selection

def activity_selection(activities):
 # Sort by end time — yeh greedy choice hai
 activities.sort(key=lambda x: x[1])

 # Pehli activity hamesha pick hogi
 result = [activities[0]]
 last_end = activities[0][1]

 # Baaki activities check karo
 for i in range(1, len(activities)):
 start, end = activities[i]
 # Agar current activity previous ke end ke baad start ho rahi hai
 if start >= last_end:
 result.append(activities[i])
 last_end = end

 return result


# Example
activities = [(1,3), (2,5), (4,7), (6,9), (8,10)]
print(activity_selection(activities))
# Output: [(1,3), (4,7), (8,10)]

Time Complexity: O(n log n) — sorting ke liye. Space Complexity: O(n) — result store karne ke liye.

Try it: code khud likho

Neeche diye gaye code editor mein activity selection ka function implement karo. Tumhe input milega — list of (start, end) tuples. Function ko return karna hai maximum non-overlapping activities ki list.

Common Mistakes

• Start time sort karna — Greedy mein hamesha end time sort karo activity selection mein. Start time sort se maximum activities nahi milengi.
• Greedy ka blindly trust karna — Har problem greedy se nahi hoti. Pehle check karo greedy choice property hold hoti hai ya nahi. Coin change mein greedy kaam nahi karta hamesha.
• Edge cases bhoolna — Empty array, single activity, overlapping sab activities — in sab ko handle karo. Function mein if not activities: return [] add karo.
• Sorting stability — Agar do activities ka end time same hai, toh start time ke hisaab se decide karo. Python mein sort stable hai lekin explicitly handle karo toh better.
• Greedy proof na karna — Interview mein hamesha batao ki kyun greedy kaam karti hai. Exchange argument se prove karo.