题目

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]输出: [[1,5]]解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

 

解题思路

• 给出的区间集合不一定有序，所以需要先进行排序
• 排序后建立新的链表，并尾插入原链表的第一个元素
• 从原链表的第二个元素进行遍历，并与新链表的最后一个元素进行比较，如果有重合的区间，则更新新链表的最后一个元素，否则，直接插入遍历到的原链表的元素

 

代码实现

package MySolution;import java.util.Collections;import java.util.Comparator;import java.util.LinkedList;import java.util.List;public class Interval {    int start;    int end;    Interval() { start = 0; end = 0; }    Interval(int s, int e) { start = s; end = e; }}class Solution {    public List
     
       merge(List
      
        intervals) {
    // 注意此处比较器接口的写法        Collections.sort(intervals, new Comparator
       
        () {            @Override            public int compare(Interval o1, Interval o2) {                if(o1.start
        
          mergediIntervals=new LinkedList
         
          (); 　　　　 // 对空表的处理（鲁棒性）        if(intervals.isEmpty()) return mergediIntervals;         mergediIntervals.add(intervals.get(0));        for(int i=1;i
         
        
       
      
     

 

代码注意事项

• 先考虑对特殊情况的处理（List空）
• 自定义排序模板：
  Collections.sort(list, new Comparator
         
          () {    @Override    public int compare(T o1, T o2) {        // TODO Auto-generated method stub        return 0;    }});