LeetCode 0352 - Data Stream as Disjoint Intervals

Reck Zhang

发布于 2021-08-11 11:32:29

1820

发布于 2021-08-11 11:32:29

Data Stream as Disjoint Intervals

Desicription

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

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, …, then the summary will be:

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

Follow up:

What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution

class SummaryRanges {
private:
    std::function<bool(std::pair<int, int>, std::pair<int, int>)> cmp = [](std::pair<int, int> a, std::pair<int, int> b) {
        if(a.first == b.first) {
            return a.second < b.second;
        }
        return a.first < b.first;
    };
    std::set<std::pair<int, int>, decltype(cmp)> set = std::set<std::pair<int, int>, decltype(cmp)>(cmp);

public:
    /** Initialize your data structure here. */
    SummaryRanges() = default;

    void addNum(int val) {
        auto it = set.lower_bound({val, val});
        int left = val;
        int right = val;
        if(it != set.begin() && (--it)->second + 1 < val) {
            it++;
        }

        while(it != set.end() && val + 1 >= it->first && val - 1 <= it->second) {
            left = std::min(left, it->first);
            right = std::max(right, it->second);
            it = set.erase(it);
        }
        set.insert(it, {left, right});
    }

    std::vector<std::vector<int>> getIntervals() {
        auto res = std::vector<std::vector<int>>();
        for(auto num : set) {
            res.push_back({num.first, num.second});
        }
        return res;
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges* obj = new SummaryRanges();
 * obj->addNum(val);
 * vector<vector<int>> param_2 = obj->getIntervals();
 */

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-06-08，如有侵权请联系 cloudcommunity@tencent.com 删除

code