我的Bilibili频道：香芋派Taro
我的个人博客：taropie0224.github.io（阅读体验更佳）
我的公众号：香芋派的烘焙坊
我的音频技术交流群：1136403177
我的个人微信：JazzyTaroPie
https://leetcode-cn.com/problems/merge-intervals/
题解
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| class Solution
{
public:
vector<vector<int> > merge(vector<vector<int> > &intervals)
{
if (intervals.size() == 0)
{
return {};
}
if (intervals.size() == 1)
{
return intervals;
}
sort(intervals.begin(), intervals.end());
vector<vector<int> > res;
for (int i = 0; i < intervals.size() - 1; i++)
{
int left = intervals[i][0], right = intervals[i][1];
int nextLeft = intervals[i + 1][0], nextRight = intervals[i + 1][1];
if (right >= nextLeft)
{
if (nextRight > right)
{
intervals[i + 1][0] = left;
intervals[i + 1][1] = nextRight;
if (i == intervals.size() - 2)
{
res.push_back({left, nextRight});
}
}
else
{
intervals[i + 1][0] = left;
intervals[i + 1][1] = right;
if (i == intervals.size() - 2)
{
res.push_back({left, right});
}
}
}
else
{
if (i < intervals.size() - 2)
{
res.push_back({left, right});
}
else
{
res.push_back({left, right});
res.push_back({nextLeft, nextRight});
}
}
}
return res;
}
};
|
思路
相邻的两个数组有三种情况，这里通过举例说明：
- [1, 4], [2, 5]，修改next为[1, 5]
- [1, 4], [2, 3]，修改next为[1, 4]
- [1, 4], [5, 6]，push_back[1, 4]
坑点：
- intervals本身长度为1或0
- 比较集合中最后两个数组时的push_back要单独考虑
