# Greedy — সিদ্ধান্তের ছবি ও পাল্টা উদাহরণ

## সর্বাধিক meeting: আগে শেষ হওয়াটি নিই

| কাজ | শুরু | শেষ | সিদ্ধান্ত |
| --- | --- | --- | --- |
| A | 1 | 3 | নিই |
| B | 2 | 5 | A-এর সঙ্গে overlap, বাদ |
| C | 3 | 6 | নিই; A শেষ হওয়ার সময় শুরু |
| D | 6 | 8 | নিই |

```mermaid
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 চলে না

```mermaid
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)`।

[ধারণায় ফিরি](concept-notes.md) · [সব সমস্যা ও অনুশীলন](problems/README.md) · [মূল উৎস](source-map.md)