leetcode.57. 插入区间（insert-interval）——两个区间相交的六种情况

柔光的暖阳◎ 2022-11-22 12:40 106阅读 0赞

# 57. 插入区间 #

给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
    输出：[[1,5],[6,9]]

示例 2：

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
    输出：[[1,2],[3,10],[12,16]]
    解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

# 代码与思路 #

先分析，[两个区间相交的六种情况][Link 1]。

两个区间相交，有六种情况

## 第一种情况，第二种情况，完全不相交 ##

假设，有两个区别`[a,b]`和`[c,d]`

或者

## 第三种情况，第四种情况，包含 ##

或者

## 第五种情况，第六种情况，相交 ##

或者

根据上面的例子可以发现有6种不同的状态，但有一半是重复的，比如`[a,b]`和`[c,d]`不相交，`[c,d]`和`[a,b]`不相交，这就可以算作是一种，只需要将这两个区间排好序就可以了，这样就省掉一半的重复情况。那么留下来的就是三种不同的情况:。

> 注意，这道题是排序好了的，所以，我们就不用再排序了。只要遍历数组，判断newInterval 的位置及是否合并等情况

## 新的区间插入情况分析 ##

这道题，“给出一个**无重叠**的 ，按照区间起始端点**排序**的区间列表”，也就是说，左端点排序过了。这里只要比较一下`newInterval`放在哪个位置就行了。

![在这里插入图片描述][20201104153029496.png_pic_center]

## 代码详解 ##

class Solution { 
        public int[][] insert(int[][] intervals, int[] newInterval) { 
            int left = newInterval[0];//合并数组左边界
            int right = newInterval[1];//合并数组右边界
            List<int[]> list = new ArrayList<>();
            boolean flag = true;//是否未添加合并的数组，true为未添加
            
    		//遍历区间
            for(int i = 0;i < intervals.length;++i){ 
                if(intervals[i][0] > right){ //在右边，不和合并数组重合
                    if(flag){ //因为在合并数组右边，如果没添加合并数组则先添加合并数组，仅添加一次
                        list.add(new int[]{ left,right});
                        flag = false;
                    }
                    list.add(intervals[i]);
                }
                if(intervals[i][1] < left){ //在合并数组左边，可添加
                    list.add(intervals[i]);
                }
                if(intervals[i][0] <= left && intervals[i][1] >= left){ //left处于数组中，可更新left
                    left = intervals[i][0];
                }
                if(intervals[i][0] <= right && intervals[i][1] >= right){ //right处于数组中，可更新right
                    right = intervals[i][1];
                }
            }
            
            //如果list为空，或者合并数组还未添加，则添加合并数组。
            //这种情况可能是intervals为空，或者合并数组在整个数组的右边。
            if(list.size() == 0 || flag){ 
                list.add(new int[]{ left,right});
            }
            
            //返回结果
            int[][] res = new int[list.size()][2];
            for(int i = 0;i < list.size();++i){ 
                res[i] = list.get(i);
            }
            return res;
        }
    }

返回结果，可以把

int[][] res = new int[list.size()][2];
     for(int i = 0;i < list.size();++i){ 
         res[i] = list.get(i);
     }
     return res;

优化为一行

return list.toArray(new int[list.size()][2]);

# 参考资料 #

[java合并区间(merge-intervals)——两个区间相交的六种情况][Link 1]

[Link 1]: https://blog.csdn.net/e891377/article/details/105559304
[20201104153029496.png_pic_center]: /images/20221120/43018c3768c745eebd0c772e77ced779.png