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.

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.

Credits:
Special thanks to @yunhong for adding this problem and creating most of the test cases.

 

这道题说有个数据流每次提供一个数字,然后让我们组成一系列分离的区间,这道题跟之前那道 Insert Interval 很像,思路也很像,每进来一个新的数字 val,都生成一个新的区间 [val, val],并且新建一个空的区间数组 res,用一个变量 cur 来保存要在现有的区间数组中加入新区间的位置。此时遍历现有的区间数组 intervals,对于每一个遍历到的当前区间 interval,假如要加入的区间的结尾位置加1比当前区间的起始位置小,说明二者不相连,将当前区间加入 res。否则当要加入区间的起始位置大于当前位置的结束位置加1,说明二者也没有交集,可以将当前区间加入 res,不过此时 cur 要自增1,因为要加入区间的位置在当前区间的后面。再否则的话,二者就会有交集,需要合并,此时用二者起始位置中较小的更新要加入区间的起始位置,同理,用二者结束位置中较大的去更新要加入区间的结束位置。最终将要加入区间放在 res 中的 cur 位置,然后将 res 赋值给 intervals 即可,参见代码如下:

 

解法一:

class SummaryRanges {
public:
    SummaryRanges() {}
    
    void addNum(int val) {
        vector<int> newInterval{val, val};
        vector<vector<int>> res;
        int cur = 0;
        for (auto interval : intervals) {
            if (newInterval[1] + 1 < interval[0]) {
                res.push_back(interval);
            } else if (newInterval[0] > interval[1] + 1) {
                res.push_back(interval);
                ++cur;
            } else {
                newInterval[0] = min(newInterval[0], interval[0]);
                newInterval[1] = max(newInterval[1], interval[1]);
            }
        }
        res.insert(res.begin() + cur, newInterval);
        intervals = res;
    }
    vector<vector<int>> getIntervals() {
        return intervals;
    }
private:
    vector<vector<int>> intervals;
};

 

感谢热心网友 greentrail 的提醒,我们可以对上面的解法进行优化。由于上面的方法每次添加区间的时候,都要把 res 赋值给 intervals,整个区间数组都要进行拷贝,十分的不高效。这里换一种方式,用一个变量 overlap 来记录所有跟要加入区间有重叠的区间的个数,用变量i表示新区间要加入的位置,这样只要最后 overlap 大于0了,现在 intervals 中将这些重合的区间删掉,然后再将新区间插入,这样就不用进行整体拷贝了,提高了效率,参见代码如下:

 

解法二:

class SummaryRanges {
public:
    SummaryRanges() {}
    
    void addNum(int val) {
        vector<int> newInterval{val, val};
        int i = 0, overlap = 0, n = intervals.size();
        for (; i < n; ++i) {
            if (newInterval[1] + 1 < intervals[i][0]) break; 
            if (newInterval[0] <= intervals[i][1] + 1) {
                newInterval[0] = min(newInterval[0], intervals[i][0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
                ++overlap;
            }
        }
        if (overlap > 0) {
            intervals.erase(intervals.begin() + i - overlap, intervals.begin() + i);
        }
        intervals.insert(intervals.begin() + i - overlap, newInterval);
    }
    vector<vector<int>> getIntervals() {
        return intervals;
    }
private:
    vector<vector<int>> intervals;
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/352

 

类似题目:

Insert Interval

Range Module

Find Right Interval 

Summary Ranges

 

参考资料:

https://leetcode.com/problems/data-stream-as-disjoint-intervals/

https://leetcode.com/problems/data-stream-as-disjoint-intervals/discuss/82557/Very-concise-c%2B%2B-solution.

https://leetcode.com/problems/data-stream-as-disjoint-intervals/discuss/82616/C%2B%2B-solution-using-map.-O(logN)-per-adding.

https://leetcode.com/problems/data-stream-as-disjoint-intervals/discuss/82553/Java-solution-using-TreeMap-real-O(logN)-per-adding.

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation