学步园

题目：

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18],（原始区间）

return [1,6],[8,10],[15,18].（最终区间）

思路：

该题是一道极角排序的类似题目。我们可以使用O（n）复杂度解决该题。

首先，定义二维数组Base[num][2]。以Base[i][0]记录以i为start的权值base；Base[i][1]记录以i为end的权值base；

base 的初始值为0，则遇到一个start就自增1，遇到一个end就自减1.则base从0 到正的那个点就一定是最终该区间的起点；而base从正到0的那个点，一定就是最终该区间的终点，此时就可以将start和end分别组装成一个最终区间（Interval）发给结果List了。由于不可能出现base为负的情况（增减守恒），所以不用考虑base从负到什么的情况。

这样，从第一个原始区间开始扫描，直到结尾既能够得到所有正确区间。

注意：如果遇到[0，0]这样的原始区间，结果也要考虑在内。

ＡＣ代码：

public List<Interval> merge(List<Interval> intervals) {

        List<Interval> rst = new LinkedList<Interval>();
        if (intervals == null || intervals.isEmpty()) {
            return rst;
        }
        int maxIdx = Integer.MIN_VALUE, minIdx = Integer.MAX_VALUE;
        for (Interval interval : intervals) {
            if (minIdx > interval.start)
                minIdx = interval.start;
            if (maxIdx < interval.end)
                maxIdx = interval.end;
        }
        int[][] Base = new int[maxIdx - minIdx + 1][2];
        for (Interval interval : intervals) {
            Base[interval.start - minIdx][0] += 1;
            Base[interval.end - minIdx][1] -= 1;
        }
        int base = 0;
        int start = 0, end = 0;
        for (int i = 0; i < Base.length; i++) {
            if (base == 0 && base + Base[i][0] != 0) {
                base += Base[i][0];
                start = i;
            } else {
                base += Base[i][0];

            }
            if (base != 0 && base + Base[i][1] == 0) {
                base += Base[i][1];
                end = i;
                rst.add(new Interval(start + minIdx, end + minIdx));
            } else {
                base += Base[i][1];
            }
        }

        return rst;
    }