Merge Intervals

最新更新请见

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(NlogN) 空间 O(N)

思路

首先根据Interval的起点，我们将其排序，这样能合并的Interval就一定是相邻的了：

[1,3] [5,6] [2,3]---> [1,3] [2,3] [5,6]

然后我们就顺序遍历这个列表，并记录一个当前待合并的Interval，如果遍历到的Interval和当前待合并的Interval有重复部分，我们就将两个合并，如果没有重复部分，就将待合并的Interval加入结果中，并用新的Interval更新这个待合并的Interval。因为数组已经排过序，前面的Interval的起点肯定小于后面Interval的起点，所以在判断是否有重叠部分时，只要考虑待合并的Interval的终点和遍历到的Interval的起点的关系就行了。

注意

• 判断重叠的边界时包含等于的情况
• 循环后还要把最后一个待合并的Interval也加入结果中
• 更新待合并Interval的边界时，要同时更新起点和终点

代码

public class Solution {    public List
    
      merge(List
     
       intervals) {        List
      
        res = new LinkedList
       
        ();        if(intervals.size() == 0){            return res;        }        // 按照起点排序        Collections.sort(intervals, new Comparator
        
         (){            public int compare(Interval i1, Interval i2){                return i1.start - i2.start;            }        });        // 拿出第一个待合并的Interval        Interval curr = intervals.get(0);        for(Interval itv : intervals){            // 如果有重叠部分，更新待合并的Interval的起点和终点            if(curr.end >= itv.start){                curr.start = Math.min(curr.start, itv.start);                curr.end = Math.max(curr.end, itv.end);            } else {            // 否则将待合并的Interval加入结果中，并选取新的待合并Interval                res.add(curr);                curr = itv;            }        }        // 将最后一个待合并的加进结果        res.add(curr);        return res;    }}
        
       
      
     
    

Insert Interval

最优解请见：

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

排序法

复杂度

时间 O(NlogN) 空间 O(N)

思路

和Merge Interval的思路接近，这题中我们只有一个待合并的Interval，就是输入给出的。我们只要把所有和该Interval有重叠的合并到一起就行了。为了方便操作，对于那些没有重叠部分的Interval，我们可以把在待合并Interval之前的Interval加入一个列表中，把之后的Interval加入另一个列表中。最后把前半部分的列表，合并后的大Interval和后半部分的列表连起来，就是结果了。

注意

• 因为待合并的Interval出现的位置不确定，判断重叠与否时既要判断起点，也要判断终点
• 原列表为空时，直接加入待合并的Interval后返回

代码

public class Solution {    public List
    
      insert(List
     
       intervals, Interval newInterval) {        List
      
        before = new LinkedList
       
        ();        List
        
          after = new LinkedList
         
          (); List
          
            res = new LinkedList
           
            (); if(intervals.size() == 0){ res.add(newInterval); return res; } // 排序 Collections.sort(intervals, new Comparator
            
             (){ public int compare(Interval i1, Interval i2){ return i1.start - i2.start; } }); for(Interval itx : intervals){ // 将待合并Interval之前的存入一个列表中 if(newInterval.start > itx.end){ before.add(itx); } // 将有重叠的Interval都合并起来 if((newInterval.end >= itx.start && newInterval.end <= itx.end) || (newInterval.start <= itx.end && newInterval.start >= itx.start)){ newInterval.start = Math.min(newInterval.start, itx.start); newInterval.end = Math.max(newInterval.end, itx.end); } // 将待合并Interval之后的存入一个列表中 if(newInterval.end < itx.start){ after.add(itx); } } // 把三部分加起来 res.addAll(before); res.add(newInterval); res.addAll(after); return res; }}