Problem
Given a collection of intervals, merge all overlapping intervals.
Example 1:
1
2
3
| Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
|
Example 2:
1
2
3
| Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.
|
Analysis
2018-09-19
这是一题关于区间操作的问题，与之前Calendar系列的题目很类似，因此思路是相似的。通过一个map记录每个关键点（包括区间的起始点和结束点）的打卡次数，去识别出重叠的区间，并将他们合并成一个区间。然后将所有的区间组成一个vector返回即可。
2020-11-18
时隔两年之后又碰上了这道题，无论是从思考还是在做法上都有了很大的不同，这里再次做一次题解，刚好可以和之前的形成对比，看到技术成长的过程。
这道题目要求的是合并重叠的区间，返回的结果是一系列不重叠的区间。首先我们对区间进行排序，排序的标准是先按起点排序，起点相同的情况下再按终点排序，这样就能够按照顺序处理区间。
使用一个新的数组记录答案，每处理一个区间，和当前答案中最后一个区间做比较。首先判断是否重叠（在有序的情况下，判断重叠的方法是对比前一个区间的终点和后一个区间的起点），如果不重叠直接把当前区间放入答案中；如果重叠的话，就需要计算出两个区间的并集，取两个区间终点中最大的作为新区间的终点（起点不需要变化）。
Solution
同样地，使用一个cursor来遍历map。在cursor为0的时候，我们认为它正处于一个区间的起始或结束，因此需要在每一个循环前先判断上一个cursor是否为0，若是，则从当前点开始是新的区间，用start记录开始位置。在cursor加上本节点的值后，如果为0，则认为当前处于区间结束点，用end记录结束位置。这样我们就能够获得一个完整的区间[start, end]。
Code
2018-09-19
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
map<int, int> records;
vector<Interval> result;
for (int i = 0; i < intervals.size(); i++) {
records[intervals[i].start]++;
records[intervals[i].end]--;
}
map<int, int>::iterator iter;
int cursor = 0;
int start = 0, end;
for(iter = records.begin(); iter != records.end(); iter++) {
if (cursor == 0) {
start = iter->first;
}
cursor += iter->second;
if (cursor == 0) {
end = iter->first;
Interval tmp = Interval(start, end);
result.emplace_back(tmp);
}
}
return result;
}
};
|
运行时间：约8ms，超过98.82%的CPP代码
2020-11-18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int size = intervals.size();
if (size == 0) {
return {};
}
sort(intervals.begin(), intervals.end());
vector<vector<int>> result;
result.push_back(intervals[0]);
for (int i = 1; i < size; i++) {
if (result.back()[1] >= intervals[i][0]) {
result.back()[1] = max(result.back()[1], intervals[i][1]);
} else {
result.push_back(intervals[i]);
}
}
return result;
}
};
|
Summary
这题已经是我做过的关于区间操作的第4道题目了，可以说在这个方面有了一定的了解。我们可以抛弃以往使用多层嵌套循环的方式来遍历判断区间，因为那样效率很低。使用map的方式反而给我们提供了一种快速的方式，其复杂度也不过是**O(n)**，同时他所能解决的问题范围也大很多，包括区间重叠、区间合并问题等。本题的分析到这里为止，谢谢您的支持！
