အခန်း ၂၀ - Greedy

နေ့စဉ်ဘဝမှာ ကျွန်တော်တို့ ဆုံးဖြတ်ချက် အများစုကို "ရှေ့ ဘယ်လောက် ဖြစ်လာမလဲ" အကုန် မတွက်ဘဲ — အခု အချိန်မှာ အကောင်းဆုံး ထင်ရတာ ကို ရွေးပြီး ဆက်သွားကြတာပါ။ ဈေးဝယ်ထွက်ရင် အသက်သာဆုံး ဆိုင်ကို ဝင်တယ်၊ အကြွေ ပြန်အမ်းရင် အကြီးဆုံး အရွက်ကို ပြန် ထုတ်ပေးတယ်။ ဒီလို "လောလောဆယ် အကောင်းဆုံးကို ရွေး" တဲ့ ချဉ်းကပ်နည်းကို algorithm ဘာသာစကားနဲ့ Greedy လို့ ခေါ်ပါတယ်။

အခန်း ၁၉ က Kruskal, Prim တွေဟာ "အခု အသက်သာဆုံး edge" ကို ရွေး၊ Dijkstra ကတော့ "start ကနေ distance အသေးဆုံး vertex" ကို ရွေးပြီး သူ့ edge တွေကို relax — အကုန်လုံး greedy algorithm တွေပါ။ တစ်ဆင့်ချင်း "လောလောဆယ် အကောင်းဆုံး" ကို ရွေးသွားတာ။ ဒီအခန်းမှာတော့ greedy ကို pattern တစ်ခု အဖြစ် သီးခြား လေ့လာပါမယ်။

Greedy ရဲ့ idea က ရိုးရှင်းပေမယ့် — အန္တရာယ် တစ်ခု ရှိတယ်။ "အခု အကောင်းဆုံး ရွေးတိုင်း — အဆုံးမှာ အကောင်းဆုံး ရတယ်" လို့ အာမ မခံနိုင်ပါ။ တစ်ခါတစ်ရံ အခုလောလောဆယ် နည်းနည်း နစ်နာပြီး ရွေးလိုက်တာက — အဆုံးမှာ ပိုကောင်းတဲ့ အဖြေ ပေးတတ်တယ်။ ဒါကြောင့် greedy ကို သင်တဲ့အခါ — code ရေးနည်းထက် "ဒီ ပြဿနာမှာ greedy တကယ် မှန်ရဲ့လား" ဆိုတဲ့ မေးခွန်းက ပိုအရေးကြီးပါတယ်။ ဒီအခန်းမှာ — greedy ဘယ်လို အလုပ်လုပ်လဲ၊ ဘယ်တော့ မှန်ပြီး ဘယ်တော့ ကျိုးလဲ၊ pattern ၂ မျိုးနဲ့ ဘယ်လို သုံးလဲ၊ ပြီးတော့ classic ပြဿနာ ၅ ခုကို လေ့လာသွားပါမယ်။

Greedy ဆိုတာ ဘာလဲ — Local vs Global

Greedy algorithm ရဲ့ အဓိက လုပ်ဆောင်ချက်ကို greedy choice လို့ ခေါ်တယ် — ဆုံးဖြတ်ချက် တစ်ဆင့်စီမှာ၊ ရှေ့မှာ ဘာဆက်ဖြစ်မလဲ မတွက်ဘဲ၊ အခု အကောင်းဆုံး ထင်ရတဲ့ option ကို ရွေးပြီး ဆက်သွားတာ။ ရွေးပြီးသား ဆုံးဖြတ်ချက်ကို နောက်ပြန် မပြင်တော့ဘူး (ဒါက back-tracking နဲ့ ကွာတဲ့ အချက်ပါ)။

ဒီနေရာမှာ နားလည်ထားရမယ့် အရေးကြီး ၂ ခု က

• Local optimum — ဆုံးဖြတ်ချက် တစ်ခုတည်း အတွက် အကောင်းဆုံး ရွေးချယ်မှု (ဥပမာ — "အခု ခြေလှမ်းမှာ အမြင့်ဆုံး ဘက်ကို တက်")။
• Global optimum — ပြဿနာ တစ်ခုလုံး အတွက် အကောင်းဆုံး အဖြေ (ဥပမာ — "တောင်ထဲက အမြင့်ဆုံး ထိပ်ကို ရောက်")။

Greedy ရဲ့ အဓိက မေးခွန်းက — "local optimum တွေ ဆက်တိုက် ရွေးသွားရင်၊ global optimum ဆီ ရောက်ရဲ့လား?" ဆိုတာပါ။ တောင်တက်တဲ့ ဥပမာနဲ့ ကြည့်ရအောင် —

   ပန်းတိုင်: အမြင့်ဆုံး ထိပ် ★ ကို ရောက်ချင်
   greedy စည်းမျဉ်း: "အခု ခြေလှမ်းမှာ အတက်ဆုံး ဘက်ကို သွား"

                          ★   ← global optimum (အမြင့်ဆုံး ထိပ်)
            ▲            /
           / \          /      ← greedy က မတ်စောက်တဲ့ ▲ ကို အရင်တက်မိ၊
          /   \____    /          local ထိပ်မှာ ပိတ် — ★ ဆီ မရောက်တော့
   ______/         \__/

ဒီဥပမာမှာ — "အခု အတက်ဆုံး ဘက် သွား" တဲ့ local choice က — ပိုနိမ့်တဲ့ တောင်ထိပ် (local optimum) မှာ ပိတ်စေပြီး၊ တကယ့် အမြင့်ဆုံး (global optimum) ★ ဆီ မရောက်ဖြစ်စေတယ်။ ဒါကြောင့် greedy ကို သုံးတိုင်း — "ဒီ ပြဿနာမှာ local ရွေးတာ global ဆီ တကယ် ရောက်ရဲ့လား" ကို သေချာ ဆုံးဖြတ် ဖို့ လိုပါတယ်။

ဘယ်တော့ Greedy အလုပ်ဖြစ်သလဲ

တောင်တက်တဲ့ ဥပမာက greedy က ရလဒ် မှန်ကန် မှု မရှိတာကို ပြတယ်။ ဒါဆို greedy ဘယ်တော့ မှန်သလဲ? ပြဿနာတစ်ခုမှာ အောက်က အချက် ၂ ခု ရှိမှ greedy က အဖြေ မှန်ပါတယ် —

1. Greedy choice property — အခု ရွေးလိုက်တဲ့ local optimum က — global optimal solution ထဲမှာ အမြဲ ပါဝင်နေတယ် ဆိုတာ သက်သေပြနိုင်ရမယ်။ တစ်နည်းပြောရင် — "အကောင်းဆုံး ရွေးချယ်မှု" ကြောင့် နောက်ပိုင်း နောင်တရစရာ မရှိ၊ ပြန်ပြင်စရာ မလို။
2. Optimal substructure — ရွေးချယ်မှု တစ်ခု လုပ်ပြီးတဲ့နောက် — ကျန်တဲ့ ပြဿနာက ပိုငယ်တဲ့ ပြဿနာ တစ်ခု ဖြစ်သွားပြီး၊ အဲ့ဒါကိုလည်း တူညီတဲ့ greedy နည်းနဲ့ ဆက်ဖြေလို့ ရရမယ်။

ဒီ ၂ ခု ရှိရင် greedy က Dynamic Programming (အခန်း ၂၂) လို possibility အကုန် မစစ်ဘဲ၊ တစ်ဆင့်ချင်း တန်းရွေးသွားလို့ ပိုမြန် (များသောအားဖြင့် $O(n)$ ဒါမှမဟုတ် $O(n \log n)$) နိုင် ပြီး memory လည်း သက်သာတယ်။ ဒါပေမယ့် အဲ့ ၂ ချက် မရှိရင် — greedy က မှားတဲ့ အဖြေ ပေးတတ်လို့၊ DP လို ပိုစေ့စပ်တဲ့ နည်းကို သုံးရတယ်။

When Greedy Fails — Coin Change ဥပမာ

Greedy မမှန်တာကို အရှင်းဆုံး ပြတဲ့ ဥပမာက အကြွေစေ့ ပြဿနာပါ။ အကြွေစေ့ အမျိုးအစား [1, 3, 4] (ကျပ်) ရှိတယ် ဆိုပါစို့ — 6 ကျပ်ကို အကြွေစေ့ အရေအတွက် အနည်းဆုံး နဲ့ ဖွဲ့ချင်တယ်။

   Greedy ("အကြီးဆုံး စေ့ အရင် ရွေး"):
        6 → 4 ယူ → ကျန် 2 → 1 ယူ → ကျန် 1 → 1 ယူ → ကျန် 0
        ရလဒ်:  4 + 1 + 1  =  ၃ စေ့

   Optimal (အမှန်):
        6 → 3 + 3  =  ၂ စေ့   ✓  (ပိုနည်း!)

Greedy က "အကြီးဆုံး 4 ကို အရင်ရွေး" တဲ့ local choice ကြောင့် — 3 + 3 ဆိုတဲ့ ပိုကောင်းတဲ့ အဖြေကို လွတ်သွားတယ်။ ဒီ denomination [1,3,4] မှာ greedy choice property မရှိလို့ — greedy က မမှန် တာပါ (ဒီလို ပြဿနာကို DP နဲ့ ဖြေရတယ် — အခန်း ၂၂)။

သိထားသင့်တာက — [1, 5, 10, 25] ဆိုတဲ့ ဒီ denomination set မှာတော့ greedy က မှန်ပါတယ် (ဒီ denomination တွေက greedy choice property ရှိနေလို့)။ ဒါပေမယ့် denomination set တိုင်းမှာ မှန်တာ မဟုတ်ဘူး — [1,3,4] လို set မျိုးမှာ မမှန် ပါဘူး။

greedy က ပြဿနာ အပေါ် မူတည်တယ်၊ သုံးခင် "မှန်မမှန်" အရင် စစ်ရမယ်။

Greedy ရဲ့ Pattern ၂ မျိုး

Greedy choice က မှန်တယ် ဆုံးဖြတ်ပြီးရင် — နောက်တစ်ဆင့်က "အဲ့ choice ကို code ထဲ ဘယ်လို အမြန် ရွေးထုတ်မလဲ" ပါ။ Real-world greedy ပြဿနာ အများစုက အောက်က pattern ၂ ခုထဲက တစ်ခုနဲ့ ဖြေလို့ ရတယ်။

၁။ Sorting + Greedy

greedy choice က အစကတည်းက ပုံသေ (ဥပမာ — "အသေးဆုံး cookie အရင်"၊ "အစောဆုံး ပြီးတဲ့ meeting အရင်") ဆိုရင် — data ကို သင့်တော်တဲ့ key နဲ့ တစ်ခါ sort လုပ်လိုက်ရုံနဲ့ — အစဉ်လိုက် တစ်ခုချင်း ရွေးသွားလို့ ရတယ်။

ဒီ pattern ရဲ့ အဓိက အလုပ်က — "ဘယ် key နဲ့ sort လုပ်ရင် greedy choice ရှင်းသွားလဲ" ကို ရှာတာပါ။ ဥပမာ — meeting scheduling မှာ start အလိုက် sort လုပ်တာထက် end အလိုက် sort လုပ်တာက ပိုအလုပ်ဖြစ်တယ် ("အစောဆုံး ပြီးတာ အရင်ရွေးရင် နောက်အတွက် နေရာ အများဆုံး ကျန်" လို့)။ Time complexity က sort ကြောင့် $O(n \log n)$ ဖြစ်လေ့ ရှိတယ်။

၂။ Priority Queue + Greedy

greedy choice က အမြဲ ပြောင်းနေတယ် ဆိုရင် (ဥပမာ — "အခု လက်ကျန် အများဆုံး task ကို run" — task တစ်ခု run ပြီးတိုင်း လက်ကျန် ပြောင်းသွား) — တစ်ခါတည်း sort လုပ်ထားလို့ မရတော့ဘူး။ အဲ့ဒီအခါ min/max heap (priority queue) ကို သုံးပြီး — အဆင့်တိုင်းမှာ "လက်ရှိ အကောင်းဆုံး" ကို ထိပ်ကနေ ဆွဲထုတ်၊ update လုပ်ပြီး ပြန်ထည့်တယ်။ heap operation တစ်ခုက $O(\log n)$ ဖြစ်လို့ — overall $O(n \log n)$ ဖြစ်လေ့ ရှိတယ်။

ဒီ pattern ၂ ခုဟာ — အခန်း ၁၁ (Sorting) နဲ့ အခန်း ၁၂ (Heap) မှာ သင်ခဲ့တဲ့ tool တွေကို greedy logic နဲ့ တွဲသုံးတာ ဖြစ်ပါတယ်။ greedy ရဲ့ "ခက်တဲ့ အပိုင်း" က algorithm မဟုတ်ဘဲ — "ဘယ် greedy choice က မှန်လဲ" ဆိုတာ မြင်တာပါ။

Real-world Examples

• Schedule Maximum Meetings — အခန်းတစ်ခုတည်းမှာ meeting အများဆုံး ထည့်ဖို့ — "အစောဆုံး ပြီးတဲ့ meeting အရင် ရွေး" (activity selection)။
• Assign Resources — server / worker အကန့်အသတ်နဲ့ — request တွေကို size အလိုက် ခွဲဝေ (greedy fit)။
• Minimize Waiting Time — queue မှာ "အချိန်တိုဆုံး job အရင် လုပ်" ဆိုရင် customer အားလုံးရဲ့ စုစုပေါင်း စောင့်ချိန် အနည်းဆုံး (shortest job first)။
• Choose Cheapest Option — flight / hotel booking မှာ "အခု အသက်သာဆုံး ရွေး"၊ retry/backoff မှာ "အရင်ဆုံး ရနိုင်တဲ့ slot ယူ"။
• Data Compression (Huffman) — character frequency အလိုက် "အကြိမ်အနည်းဆုံး ၂ ခု အရင် ပေါင်း" — priority queue + greedy (ZIP/DEFLATE နဲ့ baseline JPEG မှာ Huffman coding component အဖြစ် သုံး)။

Questions

Greedy ပြဿနာ ဖြေတဲ့အခါ — အရင်ဆုံး "ဘယ် greedy choice က မှန်မလဲ" ကို ရှာ (sort key ဒါမှမဟုတ် heap)၊ ပြီးတော့ အဲ့ choice ကို တစ်ခုချင်း လိုက်ရွေးတာပါ။ classic ၅ ခု ဖြေကြည့်ရအောင်။

၁။ Assign Cookies

ကလေး n ယောက် နဲ့ cookie m ခု ပေးထားသည် — ကလေး i မှာ ဆာလောင်မှု g[i]၊ cookie j မှာ အရွယ်အစား s[j] ရှိတယ်။ s[j] >= g[i] ဖြစ်မှ ကလေး i ကျေနပ်တယ်၊ cookie တစ်ခုကို ကလေး တစ်ယောက်ပဲ ပေးလို့ ရတယ်။ အများဆုံး ဘယ်နှယောက် ကျေနပ်စေနိုင်မလဲ။

Input: g = [1,2,3], s = [1,1]
Output: 1
   (cookie 2 ခုစလုံး size 1 — ဆာလောင်မှု 1 ကလေး တစ်ယောက်ပဲ ကျေနပ်)

ရှင်းလင်းချက်

Greedy choice: "အသေးဆုံး cookie ကို — အဲ့ဒါနဲ့ ကျေနပ်နိုင်တဲ့ ဆာလောင်မှု အနည်းဆုံး ကလေး ကို ပေး"။ ဘာကြောင့် မှန်သလဲ — cookie အသေးကို ဆာလောင်မှု အများ ကလေးဆီ ဖြုန်းပစ်ရင် နစ်နာတယ်။ ဒါကြောင့် ၂ ခုစလုံး sort (ငယ်→ကြီး) လုပ်ပြီး — pointer ၂ ခုနဲ့ "ကိုက်ရင် ၂ ဖက်တိုး၊ မကိုက်ရင် cookie ဘက်ပဲ တိုး" (two pointers)။

g = [1,2,3], s = [1,1] ကို လိုက်ကြည့်ရအောင် — (sort ပြီးသား)

j က cookie အကုန် ကုန်ပြီ → ရပ်။ ကျေနပ်တဲ့ ကလေး = i = 1 ✓

Time Complexity: $O(n \log n + m \log m)$ - sort ၂ ခု။
Space Complexity: Java in-place Arrays.sort → $O(1)$ extra (sort stack အပြင်)။

Java Solution

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);                        // ဆာလောင်မှု ငယ်→ကြီး
        Arrays.sort(s);                        // cookie size ငယ်→ကြီး
        int i = 0, j = 0;                      // i = ကလေး, j = cookie
        while (i < g.length && j < s.length) {
            if (s[j] >= g[i]) i++;             // ကိုက် — ကလေး ကျေနပ်
            j++;                               // cookie က ဘယ်လိုပဲဖြစ် ရှေ့တိုး
        }
        return i;                              // ကျေနပ်တဲ့ ကလေး အရေအတွက်
    }
}

၂။ Jump Game

array nums ပေးထားသည် — nums[i] က index i ကနေ ရှေ့သို့ အများဆုံး ခုန်နိုင်တဲ့ အကွာအဝေး။ index 0 ကစ — နောက်ဆုံး index ကို ရောက်နိုင်/မရောက်နိုင် ပြန်ပါ။

Input: nums = [2,3,1,1,4]
Output: true
   (0 →(2 ခုန်)→ 2 →... ဒါမှမဟုတ် 0→1→4  အဆုံး ရောက်)

Input: nums = [3,2,1,0,4]
Output: false
   (index 3 မှာ value 0 — ဘယ်လိုမှ ကျော်လို့ မရ၊ index 4 မရောက်)

ရှင်းလင်းချက်

Greedy choice: "အခုထိ ရောက်နိုင်တဲ့ အဝေးဆုံး index (reach) ကို မှတ်ထား၊ index တစ်ခုစီ ဖြတ်ရင်း update"။ ဘာကြောင့် မှန်သလဲ — index i ကို ရောက်နိုင်ရင် (i <= reach) — အဲ့ဒီကနေ i + nums[i] ထိ ဆက်ရောက်နိုင်တယ်။ reach က နောက်ဆုံး index ကို မီရင် true။ index i က reach ထက် ကျော်သွားရင် (i > reach) — အဲ့ဒီ index ကို ဘယ်လိုမှ မရောက်နိုင်တော့လို့ false။

nums = [2,3,1,1,4] ကို လိုက်ကြည့်ရအောင် —

Early termination: reach က နောက်ဆုံး index (n-1) ကို မီတာနဲ့ — ကျန်တဲ့ array ဆက်ဖြတ်စရာ မလိုတော့ဘဲ ချက်ချင်း true ပြန်လို့ ရတယ်။ worst case complexity မပြောင်းပေမယ့် — အဖြေ စောစော တွေ့ရင် loop အစောဆုံး ရပ်လို့ လက်တွေ့မှာ ပိုမြန်တယ်။

Time Complexity: $O(n)$ - တစ်ခေါက်ပဲ ဖြတ်။
Space Complexity: $O(1)$ - reach တစ်ခုပဲ။

Java Solution

class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;                         // အခုထိ ရောက်နိုင်တဲ့ အဝေးဆုံး
        for (int i = 0; i < nums.length; i++) {
            if (i > reach) return false;       // ဒီ index မရောက်နိုင် — ပိတ်
            reach = Math.max(reach, i + nums[i]);  // reach ကို ချဲ့
            if (reach >= nums.length - 1) return true;  // နောက်ဆုံး မီပြီ — စောစီးစွာ ရပ်
        }
        return true;                           // loop ပြီး = နောက်ဆုံး ရောက်နိုင်
    }
}

၃။ Gas Station

ဝိုင်းပတ် လမ်းကြောင်းပေါ်မှာ gas station n ခု ရှိ — station i မှာ ဆီ gas[i] ဖြည့်နိုင်၊ station i ကနေ i+1 သို့ သွားဖို့ ဆီ cost[i] ကုန်။ ဆီ ဗလာ tank နဲ့ စတင်ပြီး — ဝိုင်းတစ်ပတ် ပြန်လည်ပတ်နိုင်မယ့် စမှတ် station index ပြန်ပါ။ မဖြစ်နိုင်ရင် -1။ (အဖြေ ရှိရင် တစ်ခုတည်း ရှိမယ်လို့ အာမခံ)။

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
   (station 3 ကစ → tank: +4-1=3 → +5-2=6 → +1-3=4 → +2-4=2 → +3-5=0  ပတ်ပြီး)

ရှင်းလင်းချက်

အဓိက ၂ ချက် —

1. ဆီ စုစုပေါင်း (sum(gas)) က ကုန်ကျ စုစုပေါင်း (sum(cost)) ထက် နည်းရင် — ဘယ်ကစစ ပတ်လို့ မရ → -1။
2. Greedy: station တစ်ခုစီ ဖြတ်ရင်း tank (လက်ကျန်ဆီ) ပေါင်း — tank < 0 ဖြစ်တဲ့ နေရာ ရောက်ရင် — အဲ့ start ကနေ ဒီထိ ဘယ်နေရာကမှ start လို့ မရဘူး (ကြားထဲ ဆီ ပြတ်)။ ဒါကြောင့် start ကို နောက် station (i+1) ကို ရွှေ့ပြီး tank reset။ ဒီနည်းနဲ့ စမှတ်ကို တစ်ခေါက်တည်း ($O(n)$) နဲ့ ရှာတယ်။

gas = [1,2,3,4,5], cost = [3,4,5,1,2] ကို လိုက်ကြည့်ရအောင် —

   i   diff=gas-cost   tank (ပေါင်းပြီး)   tank<0?            start
   0     1-3 = -2          -2              ဟုတ် → reset      start=1, tank=0
   1     2-4 = -2          -2              ဟုတ် → reset      start=2, tank=0
   2     3-5 = -2          -2              ဟုတ် → reset      start=3, tank=0
   3     4-1 =  3           3              မဟုတ်             start=3
   4     5-2 =  3           6              မဟုတ်             start=3

   total = -2-2-2+3+3 = 0 ≥ 0  →  answer = start = 3 ✓

tank က index 0,1,2 မှာ နုတ်ဖြစ်လို့ start ကို တဖြည်းဖြည်း ရွှေ့သွားပြီး — index 3 ကစတော့ tank မနုတ်တော့လို့ — start 3 က အဖြေ။ total ≥ 0 ဖြစ်လို့ တကယ် ပတ်လို့ ရတယ်။

Time Complexity: $O(n)$ - တစ်ခေါက်ပဲ ဖြတ်။
Space Complexity: $O(1)$။

Java Solution

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0, tank = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            total += diff;                     // စုစုပေါင်း လက်ကျန် (ဖြစ်နိုင်/မဖြစ်)
            tank += diff;                      // လက်ရှိ start ကနေ လက်ကျန်
            if (tank < 0) {                    // ဒီထိ ပတ်လို့ မရ
                start = i + 1;                 // start ကို နောက် station ရွှေ့
                tank = 0;                      // reset
            }
        }
        return total >= 0 ? start : -1;        // total < 0 ဆို ဘယ်လိုမှ မဖြစ်
    }
}

၄။ Minimum Number of Arrows to Burst Balloons

balloon တစ်ခုစီကို 2D axis ပေါ်မှာ [start, end] (အလျားလိုက် အကျယ်) နဲ့ ပေးထားသည်။ မြှား တစ်စင်းကို x နေရာမှာ မတ်မတ် ပစ်ရင် — start <= x <= end ဖြစ်တဲ့ balloon အကုန် ပေါက်တယ်။ balloon အကုန် ပေါက်ဖို့ မြှား အနည်းဆုံး ဘယ်နှ စင်း လိုလဲ။

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
   (x=6 မှာ [1,6],[2,8] ပေါက် ;  x=12 မှာ [7,12],[10,16] ပေါက်  → ၂ စင်း)

ရှင်းလင်းချက်

ဒါက activity selection pattern ပါ — "overlap ဖြစ်တဲ့ balloon တွေကို မြှားတစ်စင်းတည်းနဲ့ ပေါက်"။ Greedy choice: balloon တွေကို end အလိုက် sort ပြီး — ပထမ balloon ရဲ့ end မှာ မြှား ပစ်။ နောက် balloon ရဲ့ start က အဲ့ မြှား x ထက် ကြီးနေမှ (overlap မဖြစ်တော့မှ) — မြှားအသစ် ထပ်ပစ်။ ဘာကြောင့် end နဲ့ sort လဲ — "အစောဆုံး ဆုံးတဲ့ balloon ရဲ့ အဆုံးမှာ ပစ်" ရင် — နောက်က overlap ဖြစ်နိုင်သမျှ အများဆုံး ပေါက်လို့။

points = [[10,16],[2,8],[1,6],[7,12]] ကို လိုက်ကြည့်ရအောင် —

   end အလိုက် sort:  [1,6]  [2,8]  [7,12]  [10,16]

   balloon     start > x ?              လုပ်ဆောင်ချက်
   [1,6]       (ပထမ)                     arrows=1,  x=6
   [2,8]       2 > 6 ? မဟုတ်             မြှား x=6 နဲ့ ပေါက်ပြီးသား (skip)
   [7,12]      7 > 6 ? ဟုတ်              arrows=2,  x=12
   [10,16]     10 > 12 ? မဟုတ်          မြှား x=12 နဲ့ ပေါက်ပြီးသား (skip)

   → မြှား 2 စင်း (x=6 နဲ့ x=12) ✓

Time Complexity: $O(n \log n)$ - sort။
Space Complexity: $O(n)$ - points က object array (int[][]) ဖြစ်လို့ Java Arrays.sort(..., comparator) (TimSort) $O(n)$ သုံး။

Java Solution

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        // end အလိုက် sort — overflow ရှောင်ဖို့ Integer.compare
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

        int arrows = 1;
        int x = points[0][1];                  // ပထမ balloon ရဲ့ end မှာ ပစ်
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > x) {            // overlap မဖြစ်တော့
                arrows++;                      // မြှား အသစ်
                x = points[i][1];
            }
        }
        return arrows;
    }
}

၅။ Task Scheduler

task တွေ (tasks — စာလုံးကြီး 'A'–'Z' character) နဲ့ cooldown n ပေးထားသည်။ CPU က unit time တစ်ခုမှာ task တစ်ခု run ၊ ဒါမှမဟုတ် idle နေနိုင်။ တူညီတဲ့ task ၂ ခုကြား အနည်းဆုံး n unit ခြားရမယ်။ task အကုန် ပြီးဖို့ အနည်းဆုံး unit time ဘယ်လောက် လိုလဲ။

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
   (A B idle  A B idle  A B  → 8 unit ;  A,A ကြား ≥2 ခြား)

ရှင်းလင်းချက်

ဒါက Priority Queue + Greedy pattern ပါ။ Greedy choice: "လက်ကျန် အများဆုံး task ကို အရင် run" — ဒါမှ frequent task ကို ဖြန့်ပြီး idle အနည်းဆုံး ဖြစ်တယ်။ "အများဆုံး" က run ပြီးတိုင်း ပြောင်းနေလို့ — max-heap နဲ့ ဆွဲထုတ်ရတယ်။

အလုပ်လုပ်ပုံ — round တစ်ခုစီမှာ slot n+1 ခု ရှိ (task + cooldown)။ round တစ်ခုစီ — heap ထဲက အများဆုံး n+1 ခုကို ဆွဲထုတ်၊ count လျှော့၊ 0 မဟုတ်သေးရင် ပြန်ထည့်။ heap ကုန်ရင် ပြီး — မကုန်သေးရင် round တစ်ခုက n+1 unit (idle ပါ)။

အရေးကြီး — round ထဲမှာ heap ကုန်ရင် break: cooldown n ကြီးပြီး task နည်းတဲ့အခါ (ဥပမာ ["A","A"], n=100) — round ထဲ slot n+1 ခု အကုန် iterate ရင် — heap ဗလာ slot တွေအတွက် အလဟဿ loop ဖြစ်ပြီး $O(N \times n)$ ဖြစ်သွားမယ်။ ဒါကြောင့် — heap ကုန်တာနဲ့ break လုပ်ပြီး round ကို ရပ်ရတယ် (idle slot တွေ မဖြုန်း)။ ဒါမှ pop အရေအတွက် စုစုပေါင်း = task N ခု ဖြစ်ပြီး $O(N)$ ရတယ်။

tasks = ["A","A","A","B","B","B"], n = 2 ကို လိုက်ကြည့်ရအောင် — (round တစ်ခု = n+1 = ၃ slot)

   freq:  A=3, B=3        heap (max): [3,3]

   round 1: A run(3→2), B run(3→2), idle      → time += 3  (heap မကုန် → n+1)
            heap ပြန်: [2,2]
   round 2: A run(2→1), B run(2→1), idle      → time += 3
            heap ပြန်: [1,1]
   round 3: A run(1→0), B run(1→0)            → time += 2  (heap ကုန် → done=2)

   စီစဉ်ပုံ:  A B _ | A B _ | A B      →  total time = 3+3+2 = 8 ✓

နောက်ဆုံး round မှာ A, B ၂ ခုပဲ ကျန်တော့ — idle မလိုဘဲ done = 2 ပဲ ပေါင်းလို့ — 9 မဟုတ်ဘဲ 8 ရတယ်။

Time Complexity: $O(N)$ - task N ခု၊ heap size ≤ 26 (constant) ဖြစ်လို့ heap op က $O(1)$။
Space Complexity: $O(1)$ - count array / heap ≤ 26။

သတိ — နောက်ဆုံး round: task ကုန်ခါနီး နောက်ဆုံး round မှာ idle မလို။ ဒါကြောင့် round တစ်ခုစီ — heap ကုန်သွားရင် တကယ် run တဲ့ task အရေအတွက် (done) ပဲ ပေါင်း၊ မကုန်သေးရင်မှ idle ပါတဲ့ n+1 ပေါင်းတယ်။

Java Solution

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freq = new int[26];
        for (char t : tasks) freq[t - 'A']++;

        // max-heap — လက်ကျန် အများဆုံး task အပေါ် (overflow ရှောင် Integer.compare)
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        for (int f : freq) if (f > 0) heap.offer(f);

        int time = 0;
        while (!heap.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int done = 0;
            for (int i = 0; i <= n; i++) {     // round = n+1 slot
                if (heap.isEmpty()) break;     // heap ကုန်ရင် ဒီ round စောစီးစွာ ရပ် (idle iteration မဖြုန်း)
                int cur = heap.poll() - 1;     // run — လက်ကျန် ၁ လျှော့
                if (cur > 0) temp.add(cur);
                done++;                        // တကယ် run တဲ့ task
            }
            for (int c : temp) heap.offer(c);  // လက်ကျန် ပြန်ထည့်
            time += heap.isEmpty() ? done : n + 1;  // နောက်ဆုံး round — idle မပါ
        }
        return time;
    }
}