2023-08-27每日一題
一、題目編號(hào)
56. 合并區(qū)間
二、題目鏈接
點(diǎn)擊跳轉(zhuǎn)到題目位置
三、題目描述
以數(shù)組 intervals 表示若干個(gè)區(qū)間的集合，其中單個(gè)區(qū)間為 intervals[i] = [starti, endi] 。請(qǐng)你合并所有重疊的區(qū)間，并返回 一個(gè)不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間 。
示例 1：
示例 2：
提示：
- 1 <= intervals.length <= 104
- intervals[i].length == 2
- 0 <= starti <= endi <= 104
四、解題代碼
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = intervals.size();
sort(intervals.begin(), intervals.end(),
[&](vector<int> &a, vector<int> &b){
return a[0] < b[0];
});
vector<vector<int>> res;
int left = intervals[0][0];
int right = intervals[0][1];
for(int i = 1; i < n; ++i){
if(intervals[i][0] <= right){
right = max(right, intervals[i][1]);
} else{
res.push_back({left, right});
left = intervals[i][0];
right = intervals[i][1];
}
}
res.push_back({left, right});
return res;
}
};
五、解題思路
(1) 首先將數(shù)組按照區(qū)間左端點(diǎn)從小到大進(jìn)行自定義排序。
(2) 接著左端設(shè)置為intervals[0][0],右端設(shè)置為 intervals[0][1]。
(3) 接著遍歷數(shù)組，如果遍歷到的區(qū)間左端大于記錄的區(qū)間的右端，則將記錄的區(qū)間放入結(jié)果數(shù)組中，新的區(qū)間更新為當(dāng)前遍歷到的區(qū)間，如果遍歷到的區(qū)間的左端小于等于記錄的區(qū)間的右端，則此時(shí)區(qū)間的右端則更新為兩者區(qū)間右端的大值。
(4) 遍歷完畢后不要忘記將當(dāng)前記錄的區(qū)間放入結(jié)果數(shù)組中。文章來源：http://www.zghlxwxcb.cn/news/detail-684047.html
(5) 最后返回結(jié)果數(shù)組即可。文章來源地址http://www.zghlxwxcb.cn/news/detail-684047.html
到了這里，關(guān)于2023-08-27 LeetCode每日一題（合并區(qū)間）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
