57. 插入区间

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

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

返回插入之后的 intervals。

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

示例 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] 重叠。

提示：

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals 根据 starti 按升序排列
newInterval.length == 2
0 <= start <= end <= 105

思路

diy
分区统计
最终AI优化版本

代码

分区统计

最终AI优化版本

class solution{
    //57. 插入区间
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int len = intervals.length;
        //----------无
        if (len == 0) {
            return new int[][]{newInterval};
        }
        //----------完全无交集
        if (intervals[0][0] > newInterval[1]) {
            int[][] result = new int[len + 1][];
            result[0] = newInterval;
            System.arraycopy(intervals, 0, result, 1, len);
            return result;
        } else if (intervals[len - 1][1] < newInterval[0]) {
            int[][] result = new int[len + 1][];
            System.arraycopy(intervals, 0, result, 0, len);
            result[len] = newInterval;
            return result;
        }
        //----------
        boolean[] flags = new boolean[len];
        int flag = -1;
        int star = -1;
        boolean ff = true;
        for (int i = 0; i < len; i++) {
            //无交集
            if (intervals[i][0] > newInterval[1] || intervals[i][1] < newInterval[0]) {
                flags[i] = true;
                flag = -1;
                if (ff && newInterval[1] < intervals[i][0]) {//获取无交集时插入的索引值
                    star = i;
                    ff = false;
                }
            } else {//有交集
                if (flag == -1) {
                    flag = i;
                    ff = false;
                    flags[i] = true;
                }
                intervals[flag][0] = Math.min(Math.min(intervals[flag][0], intervals[i][0]), newInterval[0]);
                intervals[flag][1] = Math.max(Math.max(intervals[flag][1], intervals[i][1]), newInterval[1]);
            }
        }
        for (boolean b : flags) {
            if (!b) {
                len--;
            }
        }
        if (star != -1) {
            len++;
        }
        int[][] result = new int[len][2];
        int index = 0;
        for (int i = 0; i < flags.length; i++) {
            if (i == star) {
                result[index] = newInterval;
                index++;
            }
            if (flags[i]) {
                result[index] = new int[]{intervals[i][0], intervals[i][1]};
                index++;
            }
        }
        return result;

        //分区统计
//        int n = intervals.length;
//        int[][] temp = new int[n + 1][2]; // 临时数组存储结果
//        int currentIndex = 0; // 结果数组的当前索引
//        int i = 0; // 原始数组的遍历索引
//        // 1. 处理完全在新区间左侧的区间（无重叠）
//        while (i < n && intervals[i][1] < newInterval[0]) {
//            temp[currentIndex++] = intervals[i++];
//        }
//        // 2. 处理与新区间有重叠的区间
//        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++;
//        }
//        temp[currentIndex++] = newInterval; // 添加合并后的区间
//        // 3. 处理完全在新区间右侧的区间（无重叠）
//        while (i < n) {
//            temp[currentIndex++] = intervals[i++];
//        }
//        // 创建精确大小的结果数组
//        int[][] result = new int[currentIndex][2];
//        System.arraycopy(temp, 0, result, 0, currentIndex);
//        return result;

        //最终AI优化版本
//        final int n = intervals.length;
//        if (n == 0) return new int[][]{newInterval};
//        // 预提取边界值优化访问速度
//        final int newStart = newInterval[0];
//        final int newEnd = newInterval[1];
//        // 快速路径1：新区间在所有区间之后（优化判断顺序）
//        if (newStart > intervals[n - 1][1]) {
//            int[][] res = Arrays.copyOf(intervals, n + 1);
//            res[n] = newInterval;
//            return res;
//        }
//        // 快速路径2：新区间在所有区间之前（优化判断顺序）
//        if (newEnd < intervals[0][0]) {
//            int[][] res = new int[n + 1][];
//            res[0] = newInterval;
//            System.arraycopy(intervals, 0, res, 1, n);
//            return res;
//        }
//        int mergedStart = newStart;
//        int mergedEnd = newEnd;
//        int leftCount = 0;      // 左侧不重叠区间数
//        int rightStart = n;     // 右侧区间起始位置
//        // 消除merging标志，改用mergedStart是否被修改来判断
//        boolean mergedStartSet = false;
//        // 优化后的单次遍历逻辑
//        for (int i = 0; i < n; i++) {
//            int[] curr = intervals[i];
//            // Case 1: 当前区间完全在新区间左侧
//            if (curr[1] < newStart) {
//                leftCount++;
//                continue;
//            }
//            // Case 2: 当前区间完全在新区间右侧
//            if (curr[0] > newEnd) {
//                rightStart = i;
//                break;
//            }
//            // Case 3: 重叠区间处理
//            if (!mergedStartSet) {
//                mergedStart = Math.min(curr[0], newStart);
//                mergedStartSet = true;
//            }
//            mergedEnd = Math.max(curr[1], mergedEnd); // 直接与mergedEnd比较
//        }
//        // 计算结果数组长度（统一公式）
//        final int total = leftCount + 1 + (n - rightStart);
//        int[][] res = new int[total][];
//        // 批量拷贝左侧区间（0拷贝）
//        System.arraycopy(intervals, 0, res, 0, leftCount);
//        // 处理合并/插入核心逻辑
//        res[leftCount] = mergedStartSet ? new int[]{mergedStart, mergedEnd} : newInterval;
//        // 统一右侧拷贝逻辑（包括0长度拷贝情况）
//        System.arraycopy(intervals, rightStart, res, leftCount + 1, n - rightStart);
//        return res;
    }
}