LeetCode 56. Merge Intervals（合并区间）

题目

解析

分析：这题给出一个区间，但是并不一定是有序区间，于是想到需要对区间进行排序，可以通过区间的start来排序；合并重叠只要拿下一个区间的start和end去和上一个区间的end来比较，可能有三种情况：
1、下一个区间完全包含在上一个区间中，那么下一个区间就不需要考虑了。
2、下一个区间和上一个区间部分重叠，此时需要修改上一个区间的end。
3、下一个区间和上一个区间无重叠，直接把该新区间加进去就可以了。
选择的集合：
由以上分析，基本决定排序后遍历一遍List，便可以得到结果并返回。在这里选择LinkedList是比较合适的，把新的Interval添加到链表，并在需要的时候拿最后的那个Interval和下一个遍历的Interval比较并执行添加或者修改。
comparable和comparator的选择：选择排序的方法来实现排序，先介绍一下这两个接口的区别：
comparable是一种内部比较器，让参与比较的类实现这个接口并实现 int compareTo(T o)。一般是比较者调用这个方法，传入的参数是被比较者，方法内写如何进行比较，返回负数表示比较者小于被比较者，返回0表示相等，返回正数表示比较者大于被比较者。实现这个接口的类支持Collections.sort()方法和Arrays.sort()方法。
comparator是一种一种外部比较器，它不需要被比较对象实现这个接口，而是写一个比较器的实现类，方法是 int compare(T o1, T o2)，传入两个对象，然后实现比较。它规定了某个类的对象如何比较，然后调用排序方法，但是需要传入被排序的列表以及外部比较器的实例。排序结果是从小到大的。
代码实现（java）：

class Interval {
      int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }
}
class Solution {	
	class Compare implements Comparator<Interval>{	
		public int compare(Interval o1, Interval o2) {
			return o1.start-o2.start;
		}		   
	}
    public List<Interval> merge(List<Interval> intervals) {
    	  Collections.sort(intervals, new Compare());
          LinkedList<Interval> linkedList=new LinkedList<>();
          for(Interval a: intervals){       	  
        	  if(linkedList.size()==0||linkedList.getLast().end<a.start){
        		  linkedList.add(a);
        	  }else if(linkedList.getLast().end>=a.start&&linkedList.getLast().end<a.end){
        		  linkedList.getLast().end=a.end;
        	  } 
          }
          return linkedList;                    
    }    
}