题面
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]。
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
题解
我的题解（空间最优题解）
class Solution
{
public:
vector<vector<int>> merge(vector<vector<int>>& intervals)
{
if (intervals.size() == 0)
{
return{};
}
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
vector<int> pos;
pos.push_back(0);
for (int i = 0; i + 1 < intervals.size(); i++)
{
if (intervals[i][1] >= intervals[i + 1][0])
{
intervals[i + 1][0] = intervals[i][0];
intervals[i + 1][1] = max(intervals[i][1], intervals[i + 1][1]);
pos.back() = i + 1;
}
else
{
pos.push_back(i + 1);
}
}
for (int j = 0; j < pos.size(); j++)
{
merged.push_back(intervals[pos[j]]);
}
return merged;
}
};
最速题解
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> res;
bool bMerge = true;
while (bMerge) {
bMerge = false;
for (auto data : intervals) {
bool bCheck = false;
for (auto it = res.begin(); it != res.end(); it++) {
if ((data[0] >= (*it)[0] && data[0] <= (*it)[1]) ||
(data[1] >= (*it)[0] && data[1] <= (*it)[1])) {
(*it)[0] = min(data[0], (*it)[0]);
(*it)[1] = max(data[1], (*it)[1]);
bMerge = true;
bCheck = true;
break;
}
else if ((data[0] <= (*it)[0] && data[1] >= (*it)[1]) ||
(data[0] <= (*it)[0] && data[1] >= (*it)[1])) {
(*it)[0] = min(data[0], (*it)[0]);
(*it)[1] = max(data[1], (*it)[1]);
bMerge = true;
bCheck = true;
break;
}
}
if (!bCheck) {
res.push_back(data);
//bMerge = true;
}
}
intervals = res;
res.clear();
}
return intervals;
}
};
