Chương trình tìm khoảng tốt nhất để xóa cho số khoảng còn lại nhiều nhất trong C++

Mô tả bài toán

Cho danh sách các khoảng (có thể giao nhau). Xóa một khoảng, sau đó gộp các khoảng còn lại. Tìm số khoảng còn lại lớn nhất có thể đạt được.

Ví dụ: intervals = [[5,8],[6,7],[7,10],[9,11]] → xóa [7,10] cho 2 khoảng [5,8] và [9,11].

Giải thuật (Quy hoạch động + DFS có nhớ)

1. Sắp xếp khoảng theo điểm bắt đầu.
2. Duyệt từng khoảng làm khoảng bị xóa, tính số khoảng sau khi gộp các khoảng còn lại.
3. Hàm countIntervals(i, end) trả về số khoảng từ i đến cuối, giả sử khoảng trước kết thúc tại end.
4. Dùng memoization để tránh tính lại.

Ví dụ minh họa (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);
    return 0;
}

Đầu vào

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

Đầu ra

2