LeetCode_区间问题_中等_57.插入区间
1.题目
给你一个无重叠的,按照区间起始端点排序的区间列表。
在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
示例 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] 重叠。
示例 3:
输入:intervals = [], newInterval = [5,7]
输出:[[5,7]]
示例 4:
输入:intervals = [[1,5]], newInterval = [2,3]
输出:[[1,5]]
示例 5:
输入:intervals = [[1,5]], newInterval = [2,7]
输出:[[1,7]]
提示:
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 105
intervals 根据 intervals[i][0] 按升序排列
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 105
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/insert-interval
2.思路
(1)区间问题
分析题目,先定义用于保存结果的动态数组 res,之后可将本题的求解过程分主要为以下3个阶段:将开始的非重叠区间加入res、处理插入的新区间并将有关的区间加入res、将剩余的非重叠区间加入res,具体步骤如下:
① 定义变量 left 和 right,分别表示区间 newInterval 的左右端点,此外定义初始值为 0 的变量 i,用于遍历 intervals 中的区间;
② 将开始的非重叠区间加入res:若区间intervals[i]的右端点小于left,则该区间不可能与newInterval重叠,那么将其添加到res中,然后i++,继续判断下一个区间,直到i ≥ intervals.length或者left ≤ intervals[i][1]为止;
③ 处理插入的新区间并将有关的区间加入res:
若 i ≥ intervals.length:则说明区间newInterval与任意区间intervals[i]均无重叠部分,并且intervals所有区间都已经加入到res中,此时可直接将其加入到res中,并且跳过步骤(1.4)执行(1.5)即可;
若 i<intervals.length、left ≤ intervals[i][1] 且 intervals[i][0] <= right:则说明 newInterval 至少与区间 intervals[i] 有重叠部分,此时求出当前合并区间的左右端点,即更新 left 和 right 的值,然后 i++,判断下一个区间与 [left, right] 是否有重叠部分;
最后将区间 [left, right] 加入 res 之中;
④ 将剩余的非重叠区间加入res:执行 res.add(intervals[i++]) 直到 i ≥ intervals.length;
⑤ 将 res 转换为行数为 res.size()、列数为 2 的二维数组并返回即可。
3.代码实现(Java)
//思路1————区间问题
public int[][] insert(int[][] intervals, int[] newInterval) {
int length = intervals.length;
//当intervals为空时,将newInterval作为结果的第一行返回即可
if (length == 0) {
return new int[][]{newInterval};
}
//定义res,用于保存结果
List<int[]> res = new ArrayList<>();
//left:区间newInterval的左端点 right:区间newInterval的右端点
int left = newInterval[0], right = newInterval[1];
int i = 0;
//将开始的非重叠区间加入res
//若区间intervals[i]的右端点小于left,该区间不可能与newInterval重叠,那么将其添加到res中
while (i < length && intervals[i][1] < left) {
res.add(intervals[i++]);
}
//若存在重叠区间,则求出最大合并区间的左右端点
//intervals[i][0] left ≤ intervals[i][1] right
while (i < length && intervals[i][0] <= right) {
//求出当前合并区间的左右端点,即更新 left 和 right 的值
left = Math.min(left, intervals[i][0]);
right = Math.max(right, intervals[i][1]);
//判断下一个区间与区间[left,right]是否有重叠部分
i++;
}
res.add(new int[]{left, right});
//将剩余的非重叠区间加入res
while (i < length) {
res.add(intervals[i++]);
}
//res.size():插入新区间后的区间总个数
return res.toArray(new int[res.size()][]);
}
相关文章
- Leetcode: Minimum Moves to Equal Array Elements II
- Leetcode: Kth Largest Element in an Array
- Leetcode: Remove Duplicates from Sorted Array
- [LeetCode] Longest Palindromic Substring
- [LeetCode] Remove Duplicates from Sorted Array II
- [LeetCode]剑指 Offer 55 - I. 二叉树的深度
- [LeetCode]1432. 改变一个整数能得到的最大差值
- LeetCode 35. 搜索插入位置
- [LeetCode] 978. Longest Turbulent Subarray 最长湍流子数组
- [LeetCode] 381. Insert Delete GetRandom O(1) - Duplicates allowed 常数时间内插入删除和获得随机数 - 允许重复
- [LeetCode] 377. Combination Sum IV 组合之和之四
- [LeetCode] Combination Sum III 组合之和之三
- [LeetCode] 57. Insert Interval 插入区间
- [LeetCode] 148. Sort List 链表排序
- leetcode 380. Insert Delete GetRandom O(1) O(1) 时间插入、删除和获取随机元素 (中等)
- leetcode算法35.搜索插入位置