【leetcode】57. 插入区间

题目内容

插入区间

思路分析

本题需要首先搞清楚题目的意思，一旦插入的区间与原本的区间有交集，就需要合并。

解题的核心在于考虑清楚插入区间与所遍历的区间的关系，以及考虑清楚所遇到的各种情况。

方法一：模拟

设i_l、i_r为当前正在遍历区间的左右端点值，n_l、n_r为插入区间的左右端点值。则可以确定的关系为：

i_l <= i_r
n_l <= n_r

有了以上关系，这四个量的排列组合其实就只剩六种：

case1 i_l i_r n_l n_r
case2 i_l n_l i_r n_r
case3 i_l n_l n_r i_r
case4 n_l n_r i_l i_r
case5 n_l i_l n_r i_r
case6 n_l i_l i_r n_r

case1: 当前正在遍历区间完全在插入区间左边（写条件时写成开区间），故把当前区间插入到结果中

case2: 当前区间与插入区间有交集，故把当前区间与插入区间合并为新的插入区间，即把插入区间的左端点换为当前区间的左端点

case3: 插入区间包含在当前区间中，故将当前区间插入结果中，同时标记插入区间为已插入状态

case4: 当前区间完全在插入区间的右边（写条件时写成开区间），故把当前区间插入到结果中，同时检查插入区间是否插入过，若未插入过则插入

case5: 当前区间与插入区间有交集，故把当前区间与插入区间合并为新的插入区间，即把插入区间的右端点换为当前区间的右端点

case6: 当前区间包含在插入区间中，此时不需要执行任何操作。

需要注意的点有三个：

标记是否插入过的做法
将插入区间的左右端点更新。可以这么做的原因是区间是有序且非重叠的
注意边界，如[1,3]和[3,4]是需要合并的

代码

#include <vector>
#include <math.h>
#include <limits.h>
#include <iostream>

using namespace std;

// 模拟法
// 时间复杂度O(n)
// 空间复杂度O(1)  (除存题目答案空间外)
class Solution {
public:
   vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
      vector<vector<int>> resultInterval;
      int mergeInserted = 0;

      for (auto interval : intervals) {
         if (interval[0] < newInterval[0]) {
            if (interval[1] < newInterval[0]) {
               // case1 i_l i_r n_l n_r   i插入结果中
               resultInterval.push_back(interval);
            } else if (interval[1] >= newInterval[0] && 
                       interval[1] <= newInterval[1]) {
               // case2 i_l n_l i_r n_r   i与n合并
               newInterval[0] = interval[0];
            } else {
               // case3 i_l n_l n_r i_r   i插入结果中，n包含于i
               resultInterval.push_back(interval);
               mergeInserted = 1;
            }
         } else {
            if (newInterval[1] < interval[0]) {
               // case4 n_l n_r i_l i_r   n应该已在结果内,i插入结果中
               if (!mergeInserted){
                  resultInterval.push_back(newInterval);
                  mergeInserted = 1;
               }
               resultInterval.push_back(interval);
            } else if (newInterval[1] >= interval[0] &&
                       newInterval[1] <= interval[1]) {
               // case5 n_l i_l n_r i_r   n与i合并
               newInterval[1] = interval[1];
            } else {
               // case6 n_l i_l i_r n_r   i包含于n
               ;
            }
         }
      }
      // 若遍历完还未插入，证明合并区间是最后一个区间
      if (!mergeInserted) resultInterval.push_back(newInterval);
      return resultInterval;
   }
};

int main() {
   Solution s;
   vector<vector<int>> intervals{{1,5}};
   vector<int> newInterval{ 2,7 };
   vector<vector<int>> resultInterval;
   resultInterval = s.insert(intervals, newInterval);
   cout << 1 << endl;
}

收获

提高了点逻辑思维的能力