力扣56. 合并区间

排序 + 双指针

• 思路：
  • 先对区间按左边界进行排序，然后合并重叠区域的区间；
  • 合并重叠区域的区间时可以使用双指针：
    • 将 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;
    }
};