Greedy — সিদ্ধান্তের ছবি ও পাল্টা উদাহরণ¶
সর্বাধিক meeting: আগে শেষ হওয়াটি নিই¶
| কাজ | শুরু | শেষ | সিদ্ধান্ত |
|---|---|---|---|
| A | 1 | 3 | নিই |
| B | 2 | 5 | A-এর সঙ্গে overlap, বাদ |
| C | 3 | 6 | নিই; A শেষ হওয়ার সময় শুরু |
| D | 6 | 8 | নিই |
flowchart LR
A["A: 1 থেকে 3"] --> C["C: 3 থেকে 6"] --> D["D: 6 থেকে 8"]উত্তর 3টি meeting। এখানে interval [start,end); একটি শেষ হওয়ার সময় আরেকটি শুরু করা যায়। কোনো optimal schedule-এর প্রথম meeting-এর বদলে earliest-finish meeting বসালে পরের জন্য সময় কমে না—এটাই greedy-র প্রমাণের মূল।
সব coin system-এ greedy চলে না¶
flowchart TD
A["amount 6; coin 1,3,4"] --> B["বড় coin আগে: 4+1+1"]
A --> C["অন্য নির্বাচন: 3+3"]
B --> D["3টি coin"]
C --> E["2টি coin: ভালো উত্তর"]এখানে greedy ভুল; arbitrary denomination-এর minimum coin problem-এ DP লাগতে পারে।
Median কেন absolute distance কমায়¶
মান [1,2,10]-কে target-এ আনতে প্রতি +1/−1 move-এর খরচ 1।
| target | দূরত্বের হিসাব | মোট |
|---|---|---|
| 1 | 0+1+9 | 10 |
| 2 (median) | 1+0+8 | 9 |
| 4 | 3+2+6 | 11 |
| 10 | 9+8+0 | 17 |
2 থেকে ডানে সরালে দুজনের দূরত্ব বাড়ে, একজনের কমে; মোট খরচ বাড়ে। Squared distance minimize করার প্রশ্নে median-এর এই যুক্তি ব্যবহার করবে না।
Jump Game: পৌঁছাতে পারা শেষ index¶
Array [2,3,1,1,4]।
| index i | a[i] | আগে reach | পরে max(reach,i+a[i]) |
|---|---|---|---|
| 0 | 2 | 0 | 2 |
| 1 | 3 | 2 | 4 |
শেষ index 4 পৌঁছানো যায়, এখানেই থামা যায়। কোনো ধাপে i>reach হলে i-তে যাওয়াই অসম্ভব; সেখানকার jump ব্যবহার করা যাবে না।
Gas station: ব্যর্থ অংশের পরে নতুন শুরু¶
Gas−cost মান [-2,-2,-2,3,3]।
| station | tank-এ যোগ | tank negative? | পরের candidate start |
|---|---|---|---|
| 0 | −2 | হ্যাঁ: reset 0 | 1 |
| 1 | −2 | হ্যাঁ: reset 0 | 2 |
| 2 | −2 | হ্যাঁ: reset 0 | 3 |
| 3 | +3 | না: tank 3 | 3 |
| 4 | +3 | না: tank 6 | 3 |
মোট যোগ 0, তাই global fuel যথেষ্ট। Start 3 থেকে চক্রে tank হয় 3,6,4,2,0—প্রতিটি ধাপে nonnegative।
Candy: দুই দিকের শর্ত একসঙ্গে¶
| rating | 1 | 2 | 2 | 1 |
|---|---|---|---|---|
| বাঁয়ের শর্ত | 1 | 2 | 1 | 1 |
| ডানের শর্ত | 1 | 1 | 2 | 1 |
| দুইটির max | 1 | 2 | 2 | 1 |
মোট 6টি candy; সমান rating হলে সমান candy দেওয়া বাধ্যতামূলক নয়।
একই অক্ষর পাশাপাশি না রাখা¶
AAABB সাজানো যায় [A][B][A][B][A]। AAAAB-তে 4টি A-এর মাঝখানে 3টি separator দরকার, কিন্তু B মাত্র 1টি—অসম্ভব। সাধারণ শর্ত max_frequency <= ceil(n/2)।