力扣57. 插入区间

双指针法

• 思路：
  • 用待插入区间左右边界初始化双指针 left 和 right；
  • 遍历待归并区间：
    • 如果元素整体边界在 [left, right] 左侧（item[1] < left），则将给元素插入结果数组中；
    • 如果元素整体边界在 [left, right] 右侧 （item[0] > right），则将 {left, right} 区间插入结果数组；
    • 如果在 [left, right] 之间，更新 left 和 right （左者更左，右者更右）；
  • 注意遍历完之后 {left, right} 是否插入结果数组中；

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];

        bool mark = false;
        std::vector<std::vector<int>> result;
        for (const auto & item: intervals) {
            if (item[0] > right) {
                if (!mark) {
                    result.push_back({left, right});
                    mark = true;
                }
                result.push_back(item);
            } else if (item[1] < left) {
                result.push_back(item);
            } else {
                left = std::min(left, item[0]);
                right = std::max(right, item[1]);
            }
        }

        if (!mark) {
            result.push_back({left, right});
        }

        return result;
    }
};