56. 合并區(qū)間
題目描述
以數(shù)組 intervals 表示若干個區(qū)間的集合，其中單個區(qū)間為 intervals[i] = [starti, endi] 。請你合并所有重疊的區(qū)間，并返回 一個不重疊的區(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ū)間。
提示：
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104文章來源：http://www.zghlxwxcb.cn/news/detail-686280.html
解題思路
首先將所有區(qū)間按照左區(qū)間從小到大排序，然后先將第一個區(qū)間加入結(jié)果集合，再依次從第二個區(qū)間開始遍歷，當(dāng)當(dāng)前區(qū)間的左端點小于等于結(jié)果集合的尾部區(qū)間的右端點時，表示區(qū)間之間有交集，于是開始合并區(qū)間，即更新結(jié)果集合的尾部區(qū)間的右端點為其與當(dāng)前區(qū)間的右端點兩者之間的最大值（盡可能合并較多的區(qū)間），反之則表示區(qū)間之間沒有交集，于是將當(dāng)前區(qū)間加入結(jié)果集合。文章來源地址http://www.zghlxwxcb.cn/news/detail-686280.html
class Solution {
public:
static bool cmp(vector<int> &a,vector<int> &b)
{
return a[0]<b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
// 區(qū)間排序
sort(intervals.begin(),intervals.end(),cmp);
vector<vector<int>> res;
res.push_back(intervals[0]);
// 比較[ai,bi]與[aj,bj]的bi和aj
for(int i=1;i<intervals.size();i++)
{
if(intervals[i][0]<=res.back()[1])
res.back()[1]=max(intervals[i][1],res.back()[1]);
else
res.push_back(intervals[i]);
}
return res;
}
};
到了這里，關(guān)于【每日一題】56. 合并區(qū)間的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
