Chèn khoảng (Insert Interval) trong C++

Cho tập hợp các khoảng không giao nhau, chèn một khoảng mới vào và gộp nếu cần. Ví dụ: [[1,4],[6,9]], khoảng mới [2,5] → [[1,5],[6,9]].

Giải thuật

• Thêm khoảng mới vào cuối danh sách.
• Sắp xếp theo đầu khoảng.
• Tạo mảng ans, thêm khoảng đầu tiên.
• Duyệt từ index = 1:
  • last = ans.size() - 1.
  • Nếu max(ans[last][0], ans[last][1]) < min(intervals[index][0], intervals[index][1]) → thêm intervals[index] vào ans.
  • Ngược lại: gộp khoảng → ans[last][0] = min(...), ans[last][1] = max(...).
• Trả về ans.

Ví dụ minh họa (C++)

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

void print_vector(vector<vector<int>> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << "[";
        for(int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b) {
        return a[0] < b[0];
    }
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end(), cmp);
        int n = intervals.size();
        vector<vector<int>> ans;
        ans.push_back(intervals[0]);
        int index = 1;
        while(index < n) {
            int last = ans.size() - 1;
            if(max(ans[last][0], ans[last][1]) < min(intervals[index][0], intervals[index][1])) {
                ans.push_back(intervals[index]);
            } else {
                ans[last][0] = min(ans[last][0], intervals[index][0]);
                ans[last][1] = max(ans[last][1], intervals[index][1]);
            }
            index++;
        }
        return ans;
    }
};

int main() {
    vector<vector<int>> v = {{1,4},{6,9}};
    vector<int> v1 = {2,5};
    Solution ob;
    print_vector(ob.insert(v, v1));
    return 0;
}

Đầu vào

[[1,4],[6,9]] [2,5]

Đầu ra

[[1, 5, ],[6, 9, ],]