力扣56. 合并区间

2023-12-20 09:17:04

排序 + 双指针

  • 思路:
    • 先对区间按左边界进行排序,然后合并重叠区域的区间;
    • 合并重叠区域的区间时可以使用双指针:
      • 将 left 指针设置为第一个区间的左边界,right 指针设置为第一个区间的右边界;
      • 然后探测下一个区间的左边界是否落在 [legt, right];
        • 如果落在里面,则有重叠区,可以合并,更新区域右边界;
        • 如果没有重叠,保存闭合区间;
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        std::sort(intervals.begin(), intervals.end());

        std::vector<std::vector<int>> merged;

        int size = intervals.size();
        for (int idx = 0; idx < size; ++idx) {
            int left = intervals[idx][0];
            int right = intervals[idx][1];
            while (idx + 1 < size && (right >= intervals[idx + 1][0])) {
                right = std::max(right, intervals[idx + 1][1]);
                idx++;
            }

            merged.push_back({left, right});
        }

        return merged;
    }
};

文章来源:https://blog.csdn.net/N_BenBird/article/details/135097485
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。