Sort + greedy — திட்டமிடல்

பல greedy வழிமுறைகள் வரிசைப்படுத்திய பிறகு தெளிவாகின்றன. முடிவு நேரம், மலிவான விளிம்பு, தாமதத்திற்கு நீண்ட வேலை முதல் போன்ற வடிவமைப்பை வரிசை காட்டுகிறது; பின் greedy ஒரு நேரியல் நடத்தல்.

உண்மை உலகில் இது ஏன் முக்கியம்?

புகைப்பட வரிசை: உயரத்தால் வரிசைப்படுத்தி வரிசைகளில் வைக்கலாம். விமான ஏற்றம்: மண்டலம், இருக்கை — கொள்கையை key ஆக்கி வரிசை. CPU திட்டமிடல்: கடைசி தேதி (EDD) போன்ற greedy. வடிவம்: வரிசை → முன்னுரிமை, பின் ஒரு கடவு.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

மதிப்பெண் அல்லது tuple key கண்டுபிடித்து, வரிசைப்படுத்திய பிறகு ஒவ்வொரு படியிலும் locally சிறந்த தேர்வு தெளிவாக இருக்குமா எனச் சோதிக்கவும். Exchange proof மனதில். items.sort(key=...) பின் ஒருமுறை நடத்தல். சம மதிப்புகளில் மறைமுக விதிகள் இருந்தால் stability.

Pythonில் முயற்சி செய்வோம்

# Classic interval scheduling after sorting by end time
intervals = [(1, 3), (2, 5), (4, 6), (0, 2)]
intervals.sort(key=lambda x: x[1])
end = -1
picked = []
for s, e in intervals:
    if s >= end:
        picked.append((s, e))
        end = e
print(picked)

அடிக்கடி நேரும் தவறுகள்

• தவறான key — greedy தோற்றம், உண்மையில் அல்ல.
• இயக்க நேரத்தில் மாறும் கட்டுப்பாடு — நிலையான வரிசை போதாது.
• counting போன்ற O(n) இருக்கும்போது log வரிசை.

முக்கியச் சுருக்கக் குறிப்புகள்

• வரிசை + நடத்தல் — நேர்காணல் வார்ப்புரு.
• வரிசைக்குப் பிறகு greedy எப்போது உடையும்?
• குறிப்புகளில் சிறு proof வரைபு.