Java算法题-解析 "插入区间" 算法问题

题目：

给定一个无重叠的有序区间列表，插入一个新的区间到列表中，并确保列表中的区间仍然有序且不重叠。

引言：

"插入区间" 是一个关于数组操作和区间合并的问题。解决这个问题需要对数组操作、合并区间和插入操作有深刻理解，同时需要找到一种方法来插入新区间并合并重叠的区间。通过解答这个问题，我们可以提升对数组操作、区间合并和问题规模的考虑，同时也能拓展对区间问题的解决方案。

算法思路：

我们可以使用两个指针来遍历区间列表，分别比较新区间和已有区间的关系。具体思路如下：

1. 创建一个结果列表 merged 来存储最终的合并后的区间。
2. 初始化两个指针 i 和 newInterval 分别指向区间列表的第一个区间和要插入的新区间。

3. 遍历区间列表，比较 newInterval 和当前区间的关系：

   • 如果 newInterval 的结束位置小于当前区间的起始位置，说明插入操作完成，将 newInterval 添加到 merged 列表中，并将当前区间以及后面的区间全部添加到 merged 中。
   • 如果 newInterval 的起始位置大于当前区间的结束位置，说明当前区间不受影响，将当前区间直接添加到 merged 列表中。
   • 如果 newInterval 与当前区间有重叠，更新 newInterval 的起始位置为当前区间和 newInterval 起始位置中的较小值，更新结束位置为当前区间和 newInterval 结束位置中的较大值。
4. 将指针 i 后面的所有区间都添加到 merged 列表中。

代码实现：

以下是使用 Java 实现的 "插入区间" 算法的示例代码：

import java.util.*;

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

        // Add intervals that end before newInterval starts
        while (i < n && intervals[i][1] < newInterval[0]) {
            merged.add(intervals[i]);
            i++;
        }

        // Merge overlapping intervals
        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++;
        }
        merged.add(newInterval);

        // Add remaining intervals
        while (i < n) {
            merged.add(intervals[i]);
            i++;
        }

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

算法分析：

• 时间复杂度：遍历区间列表一次，时间复杂度为 O(n)，其中 n 是区间的个数。
• 空间复杂度：需要一个结果列表 merged 来存储合并后的区间，所以空间复杂度为 O(n)。

示例和测试：

假设给定无重叠的有序区间列表 intervals = [[1,3],[6,9]] 和要插入的新区间 newInterval = [2,5]，根据算法，插入并合并后的结果为 [[1,5],[6,9]]。

我们可以使用以下代码进行测试：

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        InsertInterval solution = new InsertInterval();
        int[][] intervals = {
            {1, 3},
            {6, 9}
        };
        int[] newInterval = {2, 5};
        int[][] merged = solution.insert(intervals, newInterval);

        System.out.println("Merged intervals:");
        for (int[] interval : merged) {
            System.out.println(Arrays.toString(interval));
        }
    }
}

总结：

"插入区间" 算法题要求将新区间插入到有序的区间列表中，并确保列表中的区间仍然有序且不重叠。通过实现这个算法，我们可以提升对数组操作、合并区间和插入操作的应用，同时也能拓展对区间问题的解决方案。这个问题强调了如何使用指针和区间关系判断来插入新区间并合并重叠的区间。