352.Data Stream as Disjoint Intervals

tags: Hard,Binary Search,Design,Ordered Set

352. Data Stream as Disjoint Intervals

題目描述

Given a data stream input of non-negative integers a1, a2, ..., an, summarize the numbers seen so far as a list of disjoint intervals.

Implement the SummaryRanges class:

• SummaryRanges() Initializes the object with an empty stream.
• void addNum(int value) Adds the integer value to the stream.
• int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [
  $star{t}_i$,
  $en{d}_i$]. The answer should be sorted by
  $star{t}_i$.

範例

Example 1:

Input
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]

Explanation
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.addNum(1);      // arr = [1]
summaryRanges.getIntervals(); // return [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]

Constraints:

• 0 <= value <= 10⁴
• At most 3 * 10⁴ calls will be made to addNum and getIntervals.

Follow up: What if there are lots of merges and the number of disjoint intervals is small compared to the size of the data stream?

解答

C++

方法1

1. 先將每次拿到的數字放入一個「有序的set」
2. 因為有序，所以一個一個拿出來時檢查是否為前一個+1就好
3. 若超過前一個+1則建立新的區間

class SummaryRanges {
public:
    set<int> data;
    SummaryRanges() {
        
    }
    
    void addNum(int value) {
        data.insert(value);
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> ans;
        if (data.empty()) return ans;
        int start = *data.begin();
        int end = start;
        for (auto value : data) {
            if (value > end + 1) {
                ans.push_back({start, end});
                start = end = value;
            } else {
                end = value;
            }
        }
        ans.push_back({start, end});
        return ans;
    }
};

Yen-Chi ChenMon, Jan 30, 2023

方法2

1. 利用「有序的map」來記錄。把key當作區間的開端，value當作區間的結尾
2. 接著用binary search (upper_bound)來找到大於value的key中最小的一個。再跟前後兩個區間進行比較，來決定新的區間如何建立，以及是否移除舊的區間。

class SummaryRanges {
public:
    map<int, int> intervals;
    SummaryRanges() {
        
    }
    
    void addNum(int value) {
        int start = value, end = value;
        auto upper = intervals.upper_bound(value);
        if (upper != intervals.begin()) {
            auto target = prev(upper);
            if (target->second >= value) return;
            if (target->second + 1 == value) {
                start = target->first;
            }
        }
        if (upper != intervals.end() && upper->first == value + 1) {
            end = upper->second;
            intervals.erase(upper);
        }
        intervals[start] = end;
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> ans;
        for (const auto &interval : intervals) {
            ans.push_back({interval.first, interval.second});
        }
        return ans;
    }
};

Reference

回到題目列表