352.Data Stream as Disjoint Intervals
===

###### tags: `Hard`,`Binary Search`,`Design`,`Ordered Set`

[352. Data Stream as Disjoint Intervals](https://leetcode.com/problems/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 [$start_i$, $end_i$]. The answer should be sorted by $start_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^4^
* At most 3 * 10^4^ 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;
    }
};

> [name=Yen-Chi Chen][time=Mon, 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

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)