题目：

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。

返回插入之后的 intervals。

注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

遍历 intervals 列表，将不与 newInterval 重叠的区间直接加入结果列表。对于与 newInterval 重叠的区间，需要合并它们。具体步骤如下：

1. 初始化一个空列表 result 用于存储最终结果。
2. 遍历 intervals，对于每个区间 interval：
   • 如果 interval 在 newInterval 的左侧，不重叠，直接将 interval 加入 result。
   • 如果 interval 与 newInterval 重叠，更新 newInterval 的起始端点和结束端点，使其覆盖重叠的区间。
   • 如果 interval 在 newInterval 的右侧，不重叠，将 newInterval 加入 result，然后将 interval 加入 result。
3. 如果在遍历过程中没有将 newInterval 加入 result，说明 newInterval 在所有区间的右侧，将其加入 result。
4. 返回 result。

 

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

public class no_57 {
    public static void main(String[] args) {
        int[][] intervals = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
        int[] newInterval = {4, 8};

        int[][] re = insert(intervals, newInterval);

        for (int[] arr : re) {
            System.out.println(Arrays.toString(arr));
        }
    }

    public static int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        while (i < n && 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 < n) {
            result.add(intervals[i]);
            i++;
        }

        return result.toArray(new int[result.size()][]);
    }
}