Greedy Algorithms
Greedy Algorithm क्या होता है?
Greedy algorithm solution एक step एक बार बनाता है, हमेशा वो option चुनता है जो अभी सबसे अच्छा लगे - बिना पुराने decisions पर दोबारा सोचे। न backtracking, न आगे देखना।
यह तब काम करता है जब दो properties हों:
- Greedy choice property - locally optimal choice globally optimal solution तक ले जाए।
- Optimal substructure - हर choice के बाद बचा problem उसी problem का छोटा version हो।
Activity Selection - Classic Example
Activities दी हैं जिनके start और end times हैं। Maximum non-overlapping activities चुनो।
Greedy strategy: end time से sort करो, हमेशा सबसे पहले खत्म होने वाली activity चुनो।
def max_activities(intervals):
intervals.sort(key=lambda x: x[1])
count, end = 0, 0
for s, e in intervals:
if s >= end:
count += 1
end = e
return count
यह क्यों काम करता है? सबसे पहले खत्म होने वाली activity चुनने से बाकी activities के लिए सबसे ज़्यादा जगह बचती है।
Huffman Coding - Concept
Optimal prefix-free binary code बनाने के लिए बार-बार दो सबसे कम frequency वाले symbols merge करो। यह greedy है: हर step पर सबसे सस्ती pair merge करो। Result एक tree है जहाँ frequent symbols को short codes मिलते हैं।
Jump Game
Array दिया है जहाँ nums[i] index i से maximum jump length है। बताओ last index तक पहुँच सकते हो या नहीं।
Greedy approach: अब तक पहुँचने योग्य farthest index track करो। Left से right scan करो - अगर कभी पीछे रह गए, return false।
def can_jump(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return True
Jump Game में greedy variable 'farthest' क्या represent करता है?
Discussion
Sign in to join the discussion