Luồng dữ liệu thành các khoảng rời rạc (Data Stream as Disjoint Intervals) trong C++

Cho luồng số nguyên đầu vào, sau mỗi lần thêm số, tóm tắt các số đã thấy thành danh sách các khoảng rời rạc (disjoint intervals).

Ví dụ

Thêm lần lượt: 1, 3, 8, 2, 7

• Thêm 1: [[1,1]]
• Thêm 3: [[1,1], [3,3]]
• Thêm 8: [[1,1], [3,3], [8,8]]
• Thêm 2: [[1,3], [8,8]] (gộp 1,2,3)
• Thêm 7: [[1,3], [7,8]] (gộp 7,8)

Thuật toán

• Dùng set lưu các số đã thêm (tự động sắp xếp, không trùng).
• addNum(val): chèn vào set.
• getIntervals(): duyệt set, gộp các số liên tiếp thành khoảng.
  • Nếu khoảng cuối trong kết quả có end + 1 < x → tạo khoảng mới [x,x].
  • Ngược lại → mở rộng khoảng cuối: end++.

Cài đặt 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 SummaryRanges {
public:
    set<int> nums;
    SummaryRanges() {}

    void addNum(int val) {
        nums.insert(val);
    }

    vector<vector<int>> getIntervals() {
        vector<vector<int>> ret;
        for (int x : nums) {
            if (ret.empty() || ret.back()[1] + 1 < x) {
                ret.push_back({x, x});
            } else {
                ret.back()[1]++;
            }
        }
        return ret;
    }
};

int main() {
    SummaryRanges ob;
    ob.addNum(1); print_vector(ob.getIntervals());
    ob.addNum(3); print_vector(ob.getIntervals());
    ob.addNum(8); print_vector(ob.getIntervals());
    ob.addNum(2); print_vector(ob.getIntervals());
    ob.addNum(7); print_vector(ob.getIntervals());
    return 0;
}

Độ phức tạp

• addNum: O(log n) (chèn set).
• getIntervals: O(n) (duyệt toàn bộ set).
• Không gian: O(n).

Input / Output

Input:  addNum(1), addNum(3), addNum(8), addNum(2), addNum(7)
Output: [[1,1]], [[1,1],[3,3]], [[1,1],[3,3],[8,8]], [[1,3],[8,8]], [[1,3],[7,8]]