โปรแกรมหาช่วงที่ดีที่สุดให้ลบเพื่อให้เหลือช่วงมากที่สุดใน C++

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

ตัวอย่าง: intervals = [[5,8],[6,7],[7,10],[9,11]] ลบ [7,10] → เหลือ [5,8] และ [9,11] = 2 ช่วง (สูงสุด)

ขั้นตอนการแก้ปัญหา (DP + Memoization)

1. เรียงช่วงตามจุดเริ่มต้น
2. ฟังก์ชัน countIntervals(i, end): จำนวนช่วงจาก i ถึงสิ้นสุด โดยช่วงก่อนหน้าจบที่ end
3. Memoization ด้วย memo[i] = {min_end, count}
4. วนลูปลองลบช่วงแต่ละอัน: result = max(result, count_so_far + countIntervals(i+1, current_end))

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

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

vector<pair<int,int>> memo;

int countIntervals(vector<vector<int>>& intervals, int i, int end) {
    if (i == intervals.size()) return 0;
    if (memo[i].first < end) return INT_MIN;
    if (memo[i].first == end) return memo[i].second;
    if (end < intervals[i][0]) {
        memo[i] = {min(end, memo[i].first), 1 + countIntervals(intervals, i+1, intervals[i][1])};
        return memo[i].second;
    }
    memo[i] = {min(end, memo[i].first), countIntervals(intervals, i+1, max(intervals[i][1], end))};
    return memo[i].second;
}

int solve(vector<vector<int>>& intervals) {
    memo.clear();
    memo.resize(intervals.size(), {INT_MAX, -1});
    sort(intervals.begin(), intervals.end());
    int count = 0, result = 0, end = -1;
    for (int i = 0; i < intervals.size(); i++) {
        result = max(result, count + countIntervals(intervals, i+1, end));
        if (end < intervals[i][0]) count++;
        end = max(end, intervals[i][1]);
    }
    return result;
}

int main() {
    vector<vector<int>> v = {{5,8},{6,7},{7,10},{9,11}};
    cout << solve(v); // 2
    return 0;
}

อินพุต

{{5,8},{6,7},{7,10},{9,11}}

เอาต์พุต

2