安徽网站设计平台福州排名seo公司

双指针法

• 思路：
  • 用待插入区间左右边界初始化双指针 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;}
};