အခန်း ၂၁ - Intervals

အခန်း ၂၀ မှာ greedy ကို သင်တုန်း — "balloon ကို end အလိုက် sort ပြီး overlap မဖြစ်တော့မှ မြှားအသစ်" ဆိုတဲ့ ပြဿနာကို ဖြေခဲ့ပါတယ်။ အဲ့ဒါက interval (အပိုင်းအခြား) ပြဿနာ တစ်မျိုးပါ။ Interval ပြဿနာတွေက real-world developer အတွက် အလွန် အသုံးဝင်တယ်။ calendar booking, hotel room, subscription period, promotion date, shift schedule စတဲ့ "အချိန် / အပိုင်းအခြား" နဲ့ ဆိုင်တဲ့ feature တိုင်းမှာ တွေ့ရတယ်။

Interval ဆိုတာ — [start, end] ဆိုတဲ့ "အစ–အဆုံး အတွဲ" တစ်ခုပါ (ဥပမာ — meeting [9, 10] က ၉ နာရီကစ ၁၀ နာရီ ဆုံး)။ ဒီအခန်းမှာ — interval တွေ overlap (ထပ်) ဖြစ်/မဖြစ် ဘယ်လို စစ်လဲ၊ ဘယ်အချက်နဲ့ sort လုပ်ရင် ပြဿနာ ရှင်းသွားလဲ၊ ပြီးတော့ sweep line ဆိုတဲ့ နည်းကို မိတ်ဆက်ပြီး classic ပြဿနာ ၅ ခု ဖြေပါမယ်။

Interval ဆိုတာ ဘာလဲ — Start, End, Overlap

Interval = [start, end] — number line ပေါ်က အပိုင်းတစ်ခု။

   meeting A [1, 3]      meeting B [2, 5]
   ──●━━━━━●──────       ────●━━━━━━━━●──
     1     3                 2        5
   number line ပေါ်မှာ A နဲ့ B က  2..3  အပိုင်းမှာ ထပ်နေ (overlap)

Overlap Detection — အရေးကြီးဆုံး အခြေခံ

Interval ပြဿနာ အကုန်လုံးရဲ့ အနှစ်ချုပ်က — "interval ၂ ခု ထပ်လား မထပ်ဘူးလား" ကို စစ်တာပါ။ စည်းမျဉ်းက ရိုးရှင်းတယ် —

   A = [a1, a2],  B = [b1, b2]   (a1 ≤ a2,  b1 ≤ b2)

   overlap ဖြစ်ဖို့:   a1 ≤ b2   AND   b1 ≤ a2
   (A ရဲ့အစ က B ရဲ့အဆုံးထက် မကျော်  +  B ရဲ့အစ က A ရဲ့အဆုံးထက် မကျော်)

တစ်နည်းပြောရင် — "ထပ်မဖြစ် ဖို့က — တစ်ခုက တစ်ခုရဲ့ ရှေ့မှာ လုံးဝ ပြီးသွားရမယ်" (a2 < b1 ဒါမှမဟုတ် b2 < a1)။ ဒါမဟုတ်ရင် ထပ်တယ်။

   ထပ်တယ်:     [1,4] နဲ့ [3,6]   → 1≤6 AND 3≤4 ✓
   မထပ်ဘူး:    [1,2] နဲ့ [5,7]   → 2 < 5  (A ပြီးမှ B စ)

Sort by Start vs Sort by End

Interval ပြဿနာ အများစုကို ဖြေဖို့ — အရင်ဆုံး sort လုပ်ရတယ်။ ဘယ်အချက်နဲ့ sort လုပ်မလဲ ဆိုတာက ပြဿနာ အလိုက် ကွဲတယ် — ဒါက အရေးအကြီးဆုံး ဆုံးဖြတ်ချက်ပါ။

• Sort by start — "interval တွေကို ဘယ်ကစ ဘယ်လို တန်းစီနေလဲ" ကြည့်ချင်တဲ့အခါ — merge, insert ပြဿနာတွေအတွက်။ အစ အလိုက် စီထားရင် — ဘေးချင်း interval တွေပဲ overlap ဖြစ်နိုင်လို့ စစ်ရ လွယ်တယ်။
• Sort by end — "အများဆုံး ဘယ်နှ ခု ထပ်မဖြစ်အောင် ရွေးနိုင်လဲ" (greedy activity selection) — non-overlapping ပြဿနာတွေအတွက်။ "အစောဆုံး ပြီးတာ အရင်ရွေး" ရင် နောက်အတွက် နေရာ အများဆုံး ကျန်လို့။

မှတ်ရန်: merge / insert → start အလိုက်။ count / remove (greedy) → end အလိုက်။ ဒီ ၂ ခုကို ခွဲမှတ်ထားရင် interval ပြဿနာ အများစု ရှင်းသွားတယ်။

Sweep Line — အချိန်တန်း တစ်လျှောက် လှည့်ကြည့်ခြင်း

Sweep line ဆိုတာ — interval တွေကို တစ်ခုလုံး မကြည့်ဘဲ — number line (အချိန်တန်း) တစ်လျှောက် ဘယ်ကညာ လှည့်သွားပြီး၊ event (start / end) တစ်ခုစီမှာ "အခု တစ်ပြိုင်နက် ဘယ်နှ ခု active ဖြစ်နေလဲ" ရေတွက်တဲ့ နည်းပါ။

အဓိက idea — interval [s, e] တစ်ခုစီကို event ၂ ခု အဖြစ် ခွဲ —

• s မှာ +1 (interval တစ်ခု စ — active တိုး)
• e မှာ −1 (interval တစ်ခု ဆုံး — active လျော့)

event တွေကို အချိန်အလိုက် sort ပြီး — running count ကို ကြည့်ရင် — "တစ်ချိန်တည်းမှာ အများဆုံး ဘယ်နှ ခု ထပ်နေလဲ" ကို သိတယ်။ ဒါက meeting room အရေအတွက်, minimum platforms လို ပြဿနာတွေရဲ့ အခြေခံပါ။

   meetings: [1,4] [2,5] [7,9]

   events (sort အလိုက်):  1:+1  2:+1  4:-1  5:-1  7:+1  9:-1
   running count:          1     2     1     0     1     0
                                 ↑ အများဆုံး = 2  → အခန်း ၂ ခု လို

Real-world Examples

• Calendar Booking — Google Calendar မှာ event အသစ် ထည့်ရင် "ရှိပြီးသား event နဲ့ ထပ်လား" (overlap) စစ်တာ၊ free slot ရှာတာ။
• Hotel / Room Booking — date range [check-in, check-out] တွေ ထပ်မဖြစ်အောင်၊ ဒါမှမဟုတ် "တစ်ချိန်တည်း အခန်း ဘယ်နှ ခု လို" (sweep line) တွက်တာ။
• Subscription Active Period — user ရဲ့ subscription [start, expiry] တွေ merge လုပ်ပြီး "စုစုပေါင်း active ရက်" တွက်တာ။
• Promotion / Discount Date Range — promotion [from, to] တွေ ထပ်နေရင် merge၊ conflict ရှိမရှိ စစ်တာ။
• Employee Shift Schedule — shift [in, out] တွေ — တစ်ချိန်တည်း ဝန်ထမ်း ဘယ်နှ ယောက် လို၊ shift ထပ်နေလား စစ်တာ။

Questions

Interval ပြဿနာ ဖြေတဲ့အခါ — အရင်ဆုံး "start အလိုက် sort လား end အလိုက် sort လား" ဆုံးဖြတ်၊ ပြီးတော့ overlap rule ကို သုံးတာပါ။ classic ၅ ခု ဖြေကြည့်ရအောင်။

၁။ Merge Intervals

interval list intervals ([start, end]) ပေးထားသည်။ ထပ်နေတဲ့ (overlap) interval တွေ ပေါင်းစည်း ပြီး — ထပ်မဖြစ်တော့တဲ့ interval list ပြန်ပါ။

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
   ([1,3] နဲ့ [2,6] ထပ်နေ → [1,6] ပေါင်း)

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

Sort by start — interval တွေကို အစ အလိုက် စီလိုက်ရင် — ပေါင်းစရာ interval တွေ ဘေးချင်းကပ် လာတယ်။ ပြီးတော့ result list ထဲ တစ်ခုချင်း ထည့်ရင်း — "လက်ရှိ interval ရဲ့ start က result ရဲ့ နောက်ဆုံး interval ရဲ့ end ထက် ≤ ဆို (ထပ်)" → end ကို max နဲ့ ချဲ့၊ မထပ်ရင် interval အသစ် ထည့်။

[[1,3],[2,6],[8,10],[15,18]] ကို လိုက်ကြည့်ရအောင် — (start အလိုက် sort ပြီးသား)

→ [[1,6],[8,10],[15,18]] ✓

Time Complexity: $O(n \log n)$ - sort က dominant။
Space Complexity: $O(n)$ - result list (sort အတွက် $O(\log n)$)။

Java Solution

class Solution {
    public int[][] merge(int[][] intervals) {
        // start အလိုက် sort — overflow ရှောင် Integer.compare
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> result = new ArrayList<>();
        for (int[] cur : intervals) {
            // result ဗလာ ဒါမှမဟုတ် ထပ်မဖြစ် → interval အသစ်
            if (result.isEmpty() || cur[0] > result.get(result.size() - 1)[1]) {
                result.add(cur);
            } else {                           // ထပ် → end ချဲ့
                int[] last = result.get(result.size() - 1);
                last[1] = Math.max(last[1], cur[1]);
            }
        }
        return result.toArray(new int[0][]);
    }
}

၂။ Insert Interval

ထပ်မဖြစ်အောင် sort ထားပြီးသား interval list intervals နဲ့ — interval အသစ် newInterval ပေးထားသည်။ newInterval ကို ထည့်ပြီး — ထပ်ရင် merge လုပ်၊ ထပ်မဖြစ်တော့တဲ့ list ပြန်ပါ။

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
   ([2,5] က [1,3] နဲ့ ထပ် → [1,5] ပေါင်း)

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

list က sort ပြီးသားမို့ — အပိုင်း ၃ ပိုင်း အဖြစ် ဖြတ်တယ်။ (၁) newInterval ရဲ့ အရှေ့မှာ လုံးဝ ပြီးသွားတဲ့ interval တွေ — တိုက်ရိုက် ထည့်။ (၂) newInterval နဲ့ ထပ်တဲ့ interval တွေ — start min, end max နဲ့ ပေါင်းသွား။ (၃) newInterval ရဲ့ အနောက်က interval တွေ — တိုက်ရိုက် ထည့်။ sort ပြီးသားမို့ — sort ပြန်မလို၊ $O(n)$ နဲ့ ပြီးတယ်။

intervals = [[1,3],[6,9]], newInterval = [2,5] ကို လိုက်ကြည့်ရအောင် —

   အပိုင်း (၁) — newInterval [2,5] ရှေ့မှာ လုံးဝ ပြီးတာ (end < 2):
        [1,3] → end 3 < 2 ? မဟုတ် → ဒီအပိုင်း ဘာမှ မထည့်

   အပိုင်း (၂) — [2,5] နဲ့ ထပ်တာ (start ≤ 5) ကို ပေါင်း:
        [1,3] → start 1 ≤ 5 ? ဟုတ် → merge:  [min(2,1), max(5,3)] = [1,5]
        [6,9] → start 6 ≤ 5 ? မဟုတ် → ရပ်
        result = [[1,5]]

   အပိုင်း (၃) — ကျန်တာ တိုက်ရိုက်ထည့်:
        [6,9] → result = [[1,5],[6,9]]

   → [[1,5],[6,9]] ✓

Time Complexity: $O(n)$ - တစ်ခေါက်ပဲ ဖြတ် (sort ပြီးသား)။
Space Complexity: $O(n)$ - result list။

Java Solution

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0, n = intervals.length;

        // (၁) newInterval အရှေ့မှာ လုံးဝ ပြီးတဲ့ interval — တိုက်ရိုက်ထည့်
        while (i < n && intervals[i][1] < newInterval[0]) result.add(intervals[i++]);

        // (၂) ထပ်တဲ့ interval — start min, end max နဲ့ ပေါင်း
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

        // (၃) ကျန်တဲ့ (အနောက်က) interval — တိုက်ရိုက်ထည့်
        while (i < n) result.add(intervals[i++]);

        return result.toArray(new int[0][]);
    }
}

၃။ Meeting Rooms (Can Attend All)

meeting interval list intervals ([start, end]) ပေးထားသည်။ လူတစ်ယောက်က meeting အကုန်လုံး တက်နိုင်/မတက်နိုင် ပြန်ပါ (meeting ၂ ခု ထပ်နေရင် မတက်နိုင်)။

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false
   ([0,30] နဲ့ [5,10] ထပ်နေ → အကုန် မတက်နိုင်)

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

Sort by start — meeting တွေကို အစ အလိုက် စီပြီး — ဘေးချင်း meeting ၂ ခု ထပ်လား စစ်ရုံပါ။ "လက်ရှိ meeting ရဲ့ start က ရှေ့ meeting ရဲ့ end ထက် ငယ်ရင် (cur.start < prev.end)" → ထပ်နေ → false။ တစ်ခုမှ မထပ်ရင် true။

Time Complexity: $O(n \log n)$ - sort။
Space Complexity: $O(1)$ (sort အပြင်)။

Java Solution

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));  // start အလိုက်
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) return false;    // ထပ်နေ
        }
        return true;
    }
}

၄။ Meeting Rooms II (Minimum Rooms)

meeting interval list ပေးထားသည်။ meeting အကုန် ကျင်းပဖို့ အနည်းဆုံး အခန်း ဘယ်နှ ခု လိုလဲ ပြန်ပါ (တစ်ချိန်တည်း ထပ်နေတဲ့ meeting တွေက အခန်း သီးသန့်စီ လို)။

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
   ([0,30] တစ်ခန်း ;  [5,10] နဲ့ [15,20] က နောက်တစ်ခန်းမှာ ဆက်တိုက်  → ၂ ခန်း)

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

ဒါက sweep line ပြဿနာ ပါ — "တစ်ချိန်တည်း အများဆုံး ဘယ်နှ meeting ထပ်နေလဲ" = လိုအပ်တဲ့ အခန်း အရေအတွက်။ နည်း ၂ မျိုး —

1. Sweep line (start/end ခွဲ sort): start array နဲ့ end array ကို သီးသန့် sort၊ pointer ၂ ခုနဲ့ လိုက်ဖြတ် — meeting အသစ် စတိုင်း (start < end) အခန်းတိုး၊ ဟောင်းတစ်ခု ဆုံးရင် အခန်းပြန်လျော့။ running max = answer။
2. Min-heap: start အလိုက် sort၊ heap မှာ active meeting တွေရဲ့ end သိမ်း — meeting အသစ်ရဲ့ start က heap ထိပ် (အစောဆုံး end) ≥ ဆို → အခန်းဟောင်း ပြန်သုံး (pop)၊ မဟုတ်ရင် အခန်းသစ်။ heap size = active room။

အောက်မှာ sweep line version ပြထားတယ် (heap မလို၊ ပိုမြန်)။

[[0,30],[5,10],[15,20]] ကို လိုက်ကြည့်ရအောင် —

starts sort: [0, 5, 15]　|　ends sort: [10, 20, 30]　|　i = start pointer, j = end pointer

→ maxRooms = 2 (တစ်ချိန်တည်း အများဆုံး ၂ ခု ထပ်) ✓

Time Complexity: $O(n \log n)$ - start/end sort။
Space Complexity: $O(n)$ - start/end array။

Java Solution

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int[] starts = new int[n], ends = new int[n];
        for (int i = 0; i < n; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        Arrays.sort(starts);                   // start တွေ သီးသန့် sort
        Arrays.sort(ends);                     // end တွေ သီးသန့် sort

        int rooms = 0, maxRooms = 0, j = 0;
        for (int i = 0; i < n; i++) {
            // meeting အသစ်ရဲ့ start က အစောဆုံး end ထက် ငယ် → ထပ် → အခန်းတိုး
            if (starts[i] < ends[j]) {
                rooms++;
                maxRooms = Math.max(maxRooms, rooms);
            } else {                           // ဟောင်းတစ်ခု ဆုံးပြီ → အခန်းပြန်သုံး
                j++;
            }
        }
        return maxRooms;
    }
}

၅။ Non-overlapping Intervals

interval list ပေးထားသည်။ ကျန်တဲ့ interval တွေ ထပ်မဖြစ်တော့အောင် ဖို့ — အနည်းဆုံး ဘယ်နှ ခု ဖယ်ရှား ရမလဲ ပြန်ပါ။

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
   ([1,3] ကို ဖယ်ရင် ကျန်တာ ထပ်မဖြစ်တော့  → ၁ ခု ဖယ်)

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

ဒါက greedy activity selection ပါ — "ထပ်မဖြစ်အောင် အများဆုံး ဘယ်နှ ခု ထားနိုင်လဲ" ရှာပြီး — ကျန်တာ ဖယ်တာ။ Sort by end — "အစောဆုံး ပြီးတဲ့ interval အရင် ထား" ရင် — နောက်အတွက် နေရာ အများဆုံး ကျန်လို့ ထပ်မဖြစ်တာ အများဆုံး ထားနိုင်တယ်။ နောက် interval ရဲ့ start က ထားထားတဲ့ end ထက် ငယ်ရင် (ထပ်) → ဖယ် (count++)၊ မဟုတ်ရင် ထား (end update)။

• end အလိုက် sort။
• prevEnd ထား၊ interval တစ်ခုစီ — cur.start < prevEnd ဆို → ဖယ် (count++)၊ မဟုတ်ရင် prevEnd = cur.end။

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

   end အလိုက် sort:  [1,2]  [2,3]  [1,3]  [3,4]
                                    ↑ end 3 တူပေမယ့် ... [2,3] အရင်

   cur      prevEnd   cur.start < prevEnd ?        လုပ်ဆောင်ချက်
   [1,2]    (ပထမ)     —                            prevEnd = 2
   [2,3]    2         2 < 2 ? မဟုတ်                ထား → prevEnd = 3
   [1,3]    3         1 < 3 ? ဟုတ် (ထပ်)          ဖယ် → count = 1
   [3,4]    3         3 < 3 ? မဟုတ်                ထား → prevEnd = 4

   → ဖယ်ရတဲ့ interval = 1 ([1,3] ကို ဖယ်) ✓

Time Complexity: $O(n \log n)$ - sort။
Space Complexity: $O(1)$ (sort အပြင်)။

Java Solution

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

        int count = 0;
        int prevEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < prevEnd) {   // ထပ်နေ → ဖယ်
                count++;
            } else {                           // မထပ် → ထား
                prevEnd = intervals[i][1];
            }
        }
        return count;
    }
}