区间调度之区间合并问题
程序员文章站
2023-12-27 10:33:33
...
区间调度之区间合并问题
还是先看一道题:
一、解题思路
一个区间可以表示为 [start, end],区间重叠区间调度问题,需要按 end 排序
,以便满足贪心选择性质。而对于区间合并问题,其实按 end 和 start 排序都可以
,不过为了清晰起见,我们选择按 start 排序。
显然,对于几个相交区间合并后的结果区间 x,x.start 一定是这些相交区间中 start 最小的,x.end 一定是这些相交区间中 end 最大的。
由于已经排了序,x.start 很好确定,求 x.end 也很容易,可以类比在数组中找最大值的
过程:
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 []
# 按区间的 start 升序排列
intervals.sort(key=lambda intv: intv[0])
res = []
res.append(intervals[0])
for i in range(1, len(intervals)):
curr = intervals[i]
# res 中最后一个元素的引用
last = res[-1]
if curr[0] <= last[1]:
# 找到最大的 end
last[1] = max(last[1], curr[1])
else:
# 处理下一个待合并区间
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的每个区间按第一个元素(start)进行生序排序
sort(intervals.begin(),intervals.end(),
[&, this](vector<int> &v1, vector<int> &v2)
{
return v1[0] < v2[0];
});
//遍历整个数组
for (int i = 0; i < intervals.size(); ++i)
{
//定义一个临时变量,方便用来寻找区间的右边界
vector<int> temp = intervals[i];
//代表当前区间和intervals中的下一个区间重叠
//规定区间[start,end]
//temp[1] >= intervals[i+1][0]代表当前区间的end位置大于等于下一个区间的start位置
//如果出现第一个区间的end大于第二个区间的end,可以直接忽略,没起到任何作用
while (i + 1 < intervals.size() && temp[1] >= intervals[i+1][0])
{
//继续遍历,因为此时的右边界不一定是最优的,可能还有重叠区间
++i;
//更新区间的右边界
temp[1] = max(temp[1], intervals[i][1]);
}
//记录结果
ret.push_back(temp);
}
return ret;
}
};
至此,区间合并问题就解决了。