欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

区间调度之区间合并问题

程序员文章站 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;
    }
};

至此,区间合并问题就解决了。

相关标签: 典型例题

上一篇:

下一篇: