题解 | #牛舍扩建# java
牛舍扩建
https://www.nowcoder.com/practice/2bb8208d18344608bc6bb19a78facad9
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param intervals int整型二维数组 * @param new_interval int整型一维数组 * @return int整型二维数组 */ public int[][] insertNewInterval (int[][] intervals, int[] new_interval) { // write code here List<int[]> result = new ArrayList<>(); int index = 0; int n = intervals.length; // 添加所有结束时间早于新区间开始时间的区间 while (index < n && intervals[index][1] < new_interval[0]) { result.add(intervals[index]); index++; } // 合并与新区间重叠的区间 while (index < n && intervals[index][0] <= new_interval[1]) { new_interval[0] = Math.min(new_interval[0], intervals[index][0]); new_interval[1] = Math.max(new_interval[1], intervals[index][1]); index++; } result.add(new_interval); // 添加剩余的区间 while (index < n) { result.add(intervals[index]); index++; } return result.toArray(new int[result.size()][]); } }
Java 编程语言编写的。
该题考察的知识点包括:
- 数组操作:对二维数组进行遍历和合并操作。
- 贪心算法:通过选择当前最优的操作,逐步达到全局最优解。
代码的文字解释:
创建 result
的列表用于存储最终合并后的区间列表。
使用一个变量 index
来追踪在已有区间列表中的位置。我们遍历已有的区间列表,分为三个阶段:
- 添加所有结束时间早于新区间开始时间的区间到结果列表 result 中。这些区间不需要合并,直接添加到结果列表。
- 迭代已有的区间列表,如果当前区间与新区间有重叠,我们更新新区间的起始时间和结束时间,以确保合并后的区间能够覆盖这些重叠的区间。
- 将剩余的区间(即结束时间晚于新区间开始时间的区间)添加到结果列表中。
将合并后的结果列表转换为数组,并返回合并后的区间数组。