题目描述

给定一个非负整数的数据流输入 a₁，a₂，…，a_n，…，将到目前为止看到的数字总结为不相交的区间列表。

例如，假设数据流中的整数为 1，3，7，2，6，…，每次的总结为：

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

进阶：
如果有很多合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?

提示：
特别感谢 @yunhong 提供了本问题和其测试用例。

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

解法1

这道题我们使用TreeMap来解决。TreeMap的底层实现是R-B Tree，它的平衡性很好，对于get、put、remove、contains等操作都能够达到O(logn)的时间复杂度。我们使用的TreeMap的Key为插入操作的值，Value为能够表示插入值的最小区间。例如，我们向map中插入2，用[2,2]能够表示，用[1,3]能够表示，用[-1000,1000]也能够表示，但是我们选择最小的区间[2, 2]，这样做能做到题目要求的“目前为止看到的数字总结为不相交的区间列表“。

这里我们还用到了TreeMap提供的两个重要的操作floorEntry与ceilingEntry。floorEntry(k)返回小于等于k的最大元组；ceilingEntry(k)返回大于等于k的最小元组。我们记leftValInterval = map.floorEntry(val)，rightValInterval = map.ceilingEntry(val)。

我们将插入的值与区间已有的值的关系分为图1的6种情况。case1、case3、case5表示已有的区间能够表示插入的值，其实case5能够和case1或case3合并。case2与case4表示插入值与已有的区间连续，那么将已有的区间扩大一个单元就能够表示插入值，例如向[1, 3]插入4，向[3, 4]插入2。case6表示如果有了插入值，就能够使得已有的左右区间连续，例如向[1, 4]和[6, 9]插入5。

如果我们清晰的分析出来这些情况，编写代码就不难了。对于新插入的值val，我们首先判断他们在TreeMap中是否存在，如果存在则返回。否则，查询val的floorEntry与ceilingEntry。如果floorEntry的右边界等于val-1，就说明我们可以将val合并到floorEntry对应的区间，将区间扩大，如图1中case2所示。对于ceilingEntry的处理同理，如图1中case4所示。如果floorEntry的右边界等于val-1且ceilingEntry的左边界等于val+1，说明我们将val插入到这两个区间后，能够使得这两个区间连续，如图1中case6所示。如果不满足图1中任何一个case，说明val无法被TreeMap中已有的区间无法表示，我们需要向TreeMap插入新区间[val, val]。

全部代码如下所示，时间复杂度O(nlogn)，空间复杂度O(n)。

import java.util.Map;
import java.util.TreeMap;

class SummaryRanges {
    private TreeMap<Integer, int[]> map; // key inserted val, value the interval included the val
    /**
     * Initialize your data structure here.
     */
    public SummaryRanges() {
        map = new TreeMap<>();
    }

    public void addNum(int val) {
        if (map.containsKey(val))
            return;

        Map.Entry<Integer, int[]> leftValInterval = map.floorEntry(val);
        Map.Entry<Integer, int[]> rightValInterval = map.ceilingEntry(val);


        int[] leftInterval = leftValInterval != null ? leftValInterval.getValue() : null;
        int[] rightInterval = rightValInterval != null ? rightValInterval.getValue() : null;


        // Left or Right interval can expresses val
        if (leftInterval != null && leftInterval[0] <= val && leftInterval[1] >= val ||
                rightInterval != null && rightInterval[0] <= val && rightInterval[1] >= val)
            return;

        // merge left & right
        if (leftInterval != null && rightInterval != null && leftInterval[1] == val - 1 && rightInterval[0] == val + 1) {
            // keep left, remove right
            leftInterval[1] = rightInterval[1];
            map.remove(rightValInterval.getKey());
        } else if (leftInterval != null && leftInterval[1] == val - 1)
            leftInterval[1] = val;
        else if (rightInterval != null && rightInterval[0] == val + 1)
            rightInterval[0] = val;
        else
            map.put(val, new int[]{val, val});
    }

    public int[][] getIntervals() {
        return map.values().toArray(new int[map.size()][]);
    }
}