โปรแกรมหาจำนวนช่วงที่ต้องลบเพื่อไม่ให้ทับซ้อนใน C++

ภาพรวมปัญหา

ให้ชุดช่วง (intervals) ต้องการหาจำนวนช่วงน้อยที่สุดที่ต้องลบ เพื่อให้ช่วงที่เหลือไม่ทับซ้อนกัน

ตัวอย่าง

Input: [[8,10], [3,5], [6,9]]

Output: 1

คำอธิบาย: ลบ [6,9] เหลือ [3,5] และ [8,10] ไม่ทับซ้อน

แนวทางแก้ปัญหา (Greedy - Interval Scheduling)

เทียบเท่ากับ: หา จำนวนช่วงสูงสุดที่ไม่ทับซ้อนกัน (Maximum Non-overlapping Intervals)

คำตอบ = จำนวนช่วงทั้งหมด - จำนวนช่วงสูงสุดที่ไม่ทับซ้อน

1. เรียงช่วงตาม end time (จุดสิ้นสุด) จากน้อยไปมาก
2. เลือกช่วงแรก แล้วเลือกช่วงถัดไปที่ start ≥ end ของช่วงที่เลือกล่าสุด
3. นับจำนวนช่วงที่เลือกได้ (count)
4. คำตอบ = n - count

โค้ดตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    static bool cmp(vector& a, vector& b) {
        return a[1] < b[1]; // เรียงตาม end time
    }
    
    int eraseOverlapIntervals(vector>& intervals) {
        int n = intervals.size();
        if (n == 0) return 0;
        
        sort(intervals.begin(), intervals.end(), cmp);
        
        int count = 1;
        int end = intervals[0][1];
        
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] >= end) {
                end = intervals[i][1];
                count++;
            }
        }
        return n - count;
    }
};

int main() {
    vector> v = {{8,10}, {3,5}, {6,9}};
    Solution ob;
    cout << ob.eraseOverlapIntervals(v);
    return 0;
}

ผลลัพธ์

1

เหตุผลที่ Greedy ถูกต้อง

เลือกช่วงที่จบเร็วที่สุด ทำให้เหลือพื้นที่มากที่สุดสำหรับช่วงอื่นๆ → Optimal substructure

นี่คือปัญหา Activity Selection Problem Classic Greedy

ความซับซ้อน

• เวลา: O(N log N) — การเรียงลำดับ
• พื้นที่: O(1) หรือ O(log N) สำหรับ sorting stack

ข้อควรระวัง

• ช่วงที่มี end time เท่ากัน เรียง start time ไม่สำคัญ
• ช่วง [1,2] และ [2,3] ไม่ถือว่าทับซ้อน (end == start OK)
• ถ้าต้องการ strict non-overlapping (end < start) เปลี่ยนเงื่อนไขเป็น `>`