目錄
56. 合并區(qū)間
題目描述：
實(shí)現(xiàn)代碼與解析：
排序 + 貪心
原理思路：
56. 合并區(qū)間
題目描述：
????????以數(shù)組?intervals?表示若干個(gè)區(qū)間的集合，其中單個(gè)區(qū)間為?intervals[i] = [starti, endi]?。請(qǐng)你合并所有重疊的區(qū)間，并返回?一個(gè)不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間?。
示例 1：
輸入：intervals = [[1,3],[2,6],[8,10],[15,18]] 輸出：[[1,6],[8,10],[15,18]] 解釋：區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].
示例?2：
輸入：intervals = [[1,4],[4,5]] 輸出：[[1,5]] 解釋：區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間。
提示：文章來源：http://www.zghlxwxcb.cn/news/detail-675143.html
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
實(shí)現(xiàn)代碼與解析：
排序 + 貪心
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
// 從小到大，按左端排序
sort(intervals.begin(), intervals.end(), [&](const auto &a, auto &b){
return a[0] < b[0];
});
vector<vector<int>> res;
res.push_back(intervals[0]);
for (int i = 0; i < intervals.size(); i++)
for (int j = 0; j < 2; j++)
{
int l = intervals[i][0]; // 區(qū)間左端
int r = intervals[i][1]; // 區(qū)間右端
if (l <= res.back()[1] && r > res.back()[1]) res.back()[1] = r; // 有重疊, 但不包含
else if (l <= res.back()[1] && r <= res.back()[1]); // 有重疊，但是包含
else res.push_back({l, r}); // 無重疊
}
return res;
}
};原理思路：
????????先將區(qū)間按左端點(diǎn)排序，然后遍歷，若后區(qū)間的左端點(diǎn)小于等于前區(qū)間的右端點(diǎn)，就將兩區(qū)間合并，誰的右端點(diǎn)大就用誰的，若無重合區(qū)間，直接將區(qū)間加入結(jié)果中。??文章來源地址http://www.zghlxwxcb.cn/news/detail-675143.html
到了這里，關(guān)于LeetCode每日一題：56. 合并區(qū)間（2023.8.27 C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![LeetCode[56]合并區(qū)間](https://imgs.yssmx.com/Uploads/2024/02/653212-1.png)
