给出若干闭合区间，合并所有重叠的部分。
在线评测地址：领扣题库官网
样例1:
输入: [(1,3)]
输出: [(1,3)]样例 2:
输入: [(1,3),(2,6),(8,10),(15,18)]
输出: [(1,6),(8,10),(15,18)]解题思路
对应两个区间a, b，如何判断它们相交？
当a, b满足max(a.start,b.start)<=min(a.end,b.end)max(a.start,b.start)<=min(a.end,b.end)时，两者相交。
我们应考虑某种排序方式，使得所有相交的区间对应一段连续的数组下标，这样方便我们进行之后的合并操作。
这种排序方式应该是对区间的左端点按从小到大的方式进行排序，假设我们存在一个已经按照上面方式排序的数组：1，22，46，10。
可以看出，当我遍历数组的时候，每次访问一个区间ai，都能保证：如果ai和它前面的区间不相交，那么ai后面的任意区间都不能和ai前面的任意区间相交。这样就保证了时间复杂度为O(n)级别，即不会出现其他的遍历。
比如区间[5，7]，他和前面的区间都没有相交，他后面的所有区间和它一样，没有和[5，7]前面的区间有交集。
代码思路
- 对区间数组按区间的左端点start排序。
- 将最后的区间赋值lastinterval为intervals[0]。
- 遍历输入，如果lastinterval和当前区间相交，合并两个区间。
- 如果不相交，将lastinterval加入结果，并将lastinterval赋值为当前的区间。
复杂度分析
设区间的个数为N。
时间复杂度
- 排序的时间复杂度为O(NlogN)。
- 遍历一遍数组的时间复杂度为O(N)。
- 总时间复杂度为O(NlogN)。
空间复杂度 - 空间复杂度为O(n)，可能存在每一个区间都不与任何一段区间相交，返回的答案和传入的参数长度相等。
public class Solution {
/**
* @param intervals: interval list.
* @return: A new interval list.
*/
public List<Interval> merge(List<Interval> intervals) {
if (intervals.size() == 0) {
return intervals;
}
// 根据区间的start值排序
intervals.sort(Comparator.comparing(i -> i.start));
List<Interval> result = new ArrayList<Interval>();
Interval lastInterval = intervals.get(0);
// 如果两段区间有交集的话，合并两段区间
// 没有的话，将最后的区间加入答案，并令新的区间作为最后的区间
for (Interval interval: intervals) {
if (haveIntercation(lastInterval, interval)) {
lastInterval = mergeTwoIntervals(lastInterval, interval);
}
else {
result.add(lastInterval);
lastInterval = interval;
}
}
result.add(lastInterval);
return result;
}
// 合并两段区间
private Interval mergeTwoIntervals(Interval a, Interval b) {
return new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end));
}
// 判断区间是否有交集，要满足较大的start小于等于较小的end
private boolean haveIntercation(Interval a, Interval b) {
return Math.max(a.start, b.start) <= Math.min(a.end, b.end);
}
}
