插入区间 [算法题]

这题和我上一篇文章的合并区间题目 类似。

题目：

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

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

解题思路：

首先遍历输入区间列表，找到新区间应该插入的位置，并将之前的不重叠区间添加到结果列表中。然后，通过循环合并与新区间重叠的区间，更新新区间的起始和结束端点。最后，将新区间和之后的不重叠区间添加到结果列表中。

代码：

import java.util.ArrayList;
import java.util.List;

public class InsertInterval {

    public static int[][] insertInterval(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        
        // 添加新区间之前的不重叠区间
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }
        
        // 合并重叠区间
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);
        
        // 添加新区间之后的不重叠区间
        while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }
        
        return result.toArray(new int[result.size()][]);
    }

    public static void main(String[] args) {
        int[][] intervals1 = {{1, 3}, {6, 9}};
        int[] newInterval1 = {2, 5};
        int[][] result1 = insertInterval(intervals1, newInterval1);
        System.out.println(Arrays.deepToString(result1));

        int[][] intervals2 = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
        int[] newInterval2 = {4, 8};
        int[][] result2 = insertInterval(intervals2, newInterval2);
        System.out.println(Arrays.deepToString(result2));
    }
}