首先，需要将 intervals 进行排序，排序的依据是 interval 开始的大小。然后，将排序后的 interval 进行两两合并，如果是在合并状态中，就将当前 interval 和之前合并过的 interval 进行合并，否则尝试将当前 interval 和之前一个 interval 进行合并，在合并失败的情况下，将之前合并的结果加入 result 中。
思路比较简单，算法的时间复杂度为 O(nlogn)，空间复杂度为 O(n)，但是很奇怪，执行效率并不高，需要找到效率更高的办法。
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
38
| class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()<=1) return intervals;
sort(intervals.begin(),intervals.end(),[](vector<int> &a, vector<int> &b)->bool{
return a[0]<b[0];
});
vector<vector<int>> result;
bool isMerging=false;
int left=0,right=0;
for(int i=1;i<intervals.size();++i){
if(isMerging){
if(right>=intervals[i][0]){
isMerging=true;
left=min(left,intervals[i][0]);
right=max(right,intervals[i][1]);
}else{
isMerging=false;
result.push_back(vector<int>{left,right});
}
}else{
if(intervals[i-1][1]>=intervals[i][0]){
isMerging=true;
left=min(intervals[i-1][0],intervals[i][0]);
right=max(intervals[i-1][1],intervals[i][1]);
}else{
result.push_back(intervals[i-1]);
}
}
}
if(isMerging){
result.push_back(vector<int>{left,right});
}else{
result.push_back(intervals[intervals.size()-1]);
}
return result;
}
};
|
把思路简化了一下，直接将上一个合并过的 interval 放在 result 中，然后逐一和上一个 interval 进行合并，但依旧运行时间非常慢占用内存非常大。我怀疑是因为这道题前几天换了接口而导致的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()<=1) return intervals;
sort(intervals.begin(),intervals.end(),[](vector<int> &a, vector<int> &b)->bool{
return a[0]<b[0];
});
vector<vector<int>> result;
result.push_back(intervals[0]);
for(int i=1;i<intervals.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;
}
};
|