Merge Intervals
最后更新于：2022-04-02 01:14:13
# Merge Intervals
### Source
- leetcode: [Merge Intervals | LeetCode OJ](https://leetcode.com/problems/merge-intervals/)
- lintcode: [(156) Merge Intervals](http://www.lintcode.com/en/problem/merge-intervals/)
### Problem
Given a collection of intervals, merge all overlapping intervals.
#### Example
Given intervals => merged intervals:
~~~
[ [
[1, 3], [1, 6],
[2, 6], => [8, 10],
[8, 10], [15, 18]
[15, 18] ]
]
~~~
#### Challenge
O(n log n) time and O(1) extra space.
### 题解1 - 排序后
初次接触这道题可能会先对 interval 排序，随后考虑相邻两个 interval 的 end 和 start 是否交叉，若交叉则合并之。
### Java
~~~
/**
* Definition of Interval:
* public class Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
*/
class Solution {
/**
* @param intervals: Sorted interval list.
* @return: A new sorted interval list.
*/
public List merge(List intervals) {
if (intervals == null || intervals.isEmpty()) return intervals;
List result = new ArrayList();
// sort with Comparator
Collections.sort(intervals, new IntervalComparator());
Interval prev = intervals.get(0);
for (Interval interval : intervals) {
if (prev.end < interval.start) {
result.add(prev);
prev = interval;
} else {
prev.start = Math.min(prev.start, interval.start);
prev.end = Math.max(prev.end, interval.end);
}
}
result.add(prev);
return result;
}
private class IntervalComparator implements Comparator {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
}
}
~~~
### 源码分析
这里因为需要比较 interval 的 start, 所以需要自己实现 Comparator 接口并覆盖 compare 方法。这里取 prev 为前一个 interval。最后不要忘记加上 prev.
### 复杂度分析
排序 O(nlogn)O(n \log n)O(nlogn), 遍历 O(n)O(n)O(n), 所以总的时间复杂度为 O(nlogn)O(n \log n)O(nlogn). 空间复杂度 O(1)O(1)O(1).
### 题解2 - 插入排序
除了首先对 intervals 排序外，还可以使用类似插入排序的方法，插入的方法在题 [Insert Interval ](http://algorithm.yuanbin.me/zh-cn/problem_misc/insert_interval.html) 中已详述。这里将 result 作为 intervals 传进去即可，新插入的 interval 为 intervals 遍历得到的结果。
### Java
~~~
/**
* Definition of Interval:
* public class Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
*/
class Solution {
/**
* @param intervals: Sorted interval list.
* @return: A new sorted interval list.
*/
public List merge(List intervals) {
if (intervals == null || intervals.isEmpty()) return intervals;
List result = new ArrayList();
for (Interval interval : intervals) {
result = insert(result, interval);
}
return result;
}
private List insert(List intervals, Interval newInterval) {
List result = new ArrayList();
int insertPos = 0;
for (Interval interval : intervals) {
if (newInterval.end < interval.start) {
result.add(interval);
} else if (newInterval.start > interval.end) {
result.add(interval);
insertPos++;
} else {
newInterval.start = Math.min(newInterval.start, interval.start);
newInterval.end = Math.max(newInterval.end, interval.end);
}
}
result.add(insertPos, newInterval);
return result;
}
}
~~~
### 源码分析
关键在 insert 的理解，`result = insert(result, interval);`作为迭代生成新的 result.
### 复杂度分析
每次添加新的 interval 都是线性时间复杂度，故总的时间复杂度为 O(1+2+...+n)=O(n2)O(1 + 2 + ... + n) = O(n^2)O(1+2+...+n)=O(n2). 空间复杂度为 O(n)O(n)O(n).
### Reference
- [Merge Intervals 参考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/merge-intervals/)
- Soulmachine 的 leetcode 题解
';