LC56. Merge Intervals

思路：

会出现的情况：

相交：[0, 4] [2, 3]; [0, 3] [1,4]

不相交

先将所有数组进行排列，按照start的值从小到大排，如果start相等，按照end的值从小到大排

所以if 不相交， 即interval.end < interval2.start; 进行list.add(interval), interval = interval2

else就是相交的两种情况interval.end > interval2.end & interval.end > interval2.start 但< interval2.end

进行new interval(start = interval.start, end = Math.max(interval2.end, interval.end)

list.add(interval)

时间复杂度：排序是binarysearchO(nlogn)， 遍历是O(n)，所以时间复杂度是O(nlogn)，空间复杂度O(1)

知识点：

http://www.cnblogs.com/duange/p/6135943.html

Comparable和camparator compareTo:

comparator的compare会告诉代码怎么排序

Collections.sort用法：Collections.sort(list, new Comparator<Dog>)