區(qū)間調(diào)度之區(qū)間合并問題

還是先看一道題：

一、解題思路

一個(gè)區(qū)間可以表示為 [start, end]，區(qū)間重疊區(qū)間調(diào)度問題，需要按 end 排序，以便滿足貪心選擇性質(zhì)。而對于區(qū)間合并問題，其實(shí)按 end 和 start 排序都可以，不過為了清晰起見，我們選擇按 start 排序。

顯然，對于幾個(gè)相交區(qū)間合并后的結(jié)果區(qū)間 x，x.start 一定是這些相交區(qū)間中 start 最小的，x.end 一定是這些相交區(qū)間中 end 最大的。

由于已經(jīng)排了序，x.start 很好確定，求 x.end 也很容易，可以類比在數(shù)組中找最大值的過程：

int max_ele = arr[0]; for (int i = 1; i < arr.length; i++) max_ele = max(max_ele, arr[i]); return max_ele;

二、完整代碼

# intervals 形如 [[1,3],[2,6]...] def merge(intervals):if not intervals: return []# 按區(qū)間的 start 升序排列intervals.sort(key=lambda intv: intv[0])res = []res.append(intervals[0])for i in range(1, len(intervals)):curr = intervals[i]# res 中最后一個(gè)元素的引用last = res[-1]if curr[0] <= last[1]:# 找到最大的 endlast[1] = max(last[1], curr[1])else:# 處理下一個(gè)待合并區(qū)間res.append(curr)return res

C++代碼：

class Solution { public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> ret;if(intervals.empty()){return ret;}//先對intervals的每個(gè)區(qū)間按第一個(gè)元素（start）進(jìn)行生序排序sort(intervals.begin(),intervals.end(),[&, this](vector<int> &v1, vector<int> &v2) { return v1[0] < v2[0];});//遍歷整個(gè)數(shù)組for (int i = 0; i < intervals.size(); ++i) {//定義一個(gè)臨時(shí)變量，方便用來尋找區(qū)間的右邊界vector<int> temp = intervals[i];//代表當(dāng)前區(qū)間和intervals中的下一個(gè)區(qū)間重疊//規(guī)定區(qū)間[start,end]//temp[1] >= intervals[i+1][0]代表當(dāng)前區(qū)間的end位置大于等于下一個(gè)區(qū)間的start位置//如果出現(xiàn)第一個(gè)區(qū)間的end大于第二個(gè)區(qū)間的end，可以直接忽略，沒起到任何作用while (i + 1 < intervals.size() && temp[1] >= intervals[i+1][0]) {//繼續(xù)遍歷，因?yàn)榇藭r(shí)的右邊界不一定是最優(yōu)的，可能還有重疊區(qū)間++i;//更新區(qū)間的右邊界temp[1] = max(temp[1], intervals[i][1]);}//記錄結(jié)果ret.push_back(temp);}return ret;} };

至此，區(qū)間合并問題就解決了。

總結(jié)

以上是生活随笔為你收集整理的区间调度之区间合并问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。