合并区间（LintCode）

阅读量：6504 次

发布时间：2019-06-24

本文共 2138 字，大约阅读时间需要 7 分钟。

合并区间

给出若干闭合区间，合并所有重叠的部分。

样例

给出的区间列表 => 合并后的区间列表：

[                     [  [1, 3],               [1, 6],  [2, 6],      =>       [8, 10],  [8, 10],              [15, 18]  [15, 18]            ]]

挑战

O(n log n) 的时间和 O(1) 的额外空间。

思路是清晰的，代码是混乱的。先用Collection.sort()方法对List排序。当然也可以先toArray()然后用Arrays.sort()排序。但是都需要写一个实现Comparator接口的内部类。

1 /** 2  * Definition of Interval: 3  * public class Interval { 4  *     int start, end; 5  *     Interval(int start, int end) { 6  *         this.start = start; 7  *         this.end = end; 8  *     } 9  */10 11 class Solution {12     /**13      * @param intervals: Sorted interval list.14      * @return: A new sorted interval list.15      */16      17     public class IntervalCmp implements Comparator
        
          {18         public int compare(Interval i1, Interval i2) {19             if (i1.start < i2.start) return -1;20             if (i1.start == i2.start && i1.end <= i2.end) return -1;21             return 1;22         }23      }24     public List
         
           merge(List
          
            intervals) {25         if(intervals.size() == 1)return intervals;26         List
           
             list = new ArrayList
            
             ();27         int max1 = -1;28         int min1 = 99999999;29         int max = -1;30         int min = 99999999;31         32         //借助Collections。sort()排序，百度了一下JDK7不加上这句的话可能会报错33         System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");34         Collections.sort(intervals, new IntervalCmp());35         36         for(int i = 0;i
             
               max1 || x.end < min1) {39 min = x.start;40 max = x.end;41 for(int j = i+1;j
              
               = min && y.start <= max) {44 if(max < y.end) {45 max = y.end;46 }47 if(min > y.start) {48 min = y.start;49 }50 }51 }52 x.end = max;53 x.start = min;54 if(max1 < max) max1 = max;55 if(min1 > min) min1 = min;56 list.add(x);57 }58 }59 return list;60 }61 62 }