内容介绍
给你一个 无重叠的 ,按照区间起始端点排序的区间列表
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
完整代码
int** insert(int** intervals, int intervalsSize, int* intervalsColSize, int* newInterval, int newIntervalSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
int left = newInterval[0];
int right = newInterval[1];
bool placed = false;
int** ans = malloc(sizeof(int*) * (intervalsSize + 1));
*returnColumnSizes = malloc(sizeof(int*) * (intervalsSize + 1));
for (int i = 0; i < intervalsSize; ++i) {
int* interval = intervals[i];
if (interval[0] > right) {
// 在插入区间的右侧且无交集
if (!placed) {
int* tmp = malloc(sizeof(int) * 2);
tmp[0] = left, tmp[1] = right;
(*returnColumnSizes)[*returnSize] = 2;
ans[(*returnSize)++] = tmp;
placed = true;
}
int* tmp = malloc(sizeof(int) * 2);
memcpy(tmp, interval, sizeof(int) * 2);
(*returnColumnSizes)[*returnSize] = 2;
ans[(*returnSize)++] = tmp;
} else if (interval[1] < left) {
// 在插入区间的左侧且无交集
int* tmp = malloc(sizeof(int) * 2);
memcpy(tmp, interval, sizeof(int) * 2);
(*returnColumnSizes)[*returnSize] = 2;
ans[(*returnSize)++] = tmp;
} else {
// 与插入区间有交集,计算它们的并集
left = fmin(left, interval[0]);
right = fmax(right, interval[1]);
}
}
if (!placed) {
int* tmp = malloc(sizeof(int) * 2);
tmp[0] = left, tmp[1] = right;
(*returnColumnSizes)[*returnSize] = 2;
ans[(*returnSize)++] = tmp;
}
return ans;
}
思路详解
一、问题背景
给定一个二维数组intervals
,其中每个子数组表示一个区间,我们需要合并这些区间,使得没有重叠的区间尽可能紧密相连。同时,我们有一个新的区间newInterval
,需要将其插入到intervals
中。
二、解题思路
-
排序:
- 首先,我们需要对
intervals
数组进行排序。排序的依据是每个子数组的第一个元素,因为合并的目的是让没有重叠的区间尽可能紧密相连。
- 首先,我们需要对
-
插入新区间:
- 创建一个
List<int[]>
,用于存储合并后的区间。 - 遍历排序后的
intervals
数组,对于每个区间,根据合并策略添加或更新列表中的区间。 - 同时,插入新区间
newInterval
,根据新区间与当前区间的相对位置,决定是否需要更新列表中的区间。
- 创建一个
-
返回结果:
- 遍历完成后,将
List<int[]>
转换为二维数组并返回。
- 遍历完成后,将
三、代码详解
- 排序:
- 使用
Arrays.sort
方法对intervals
数组进行排序,比较器比较的是每个子数组的第一个元素。
- 使用
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] interval1, int[] interval2) {
return interval1[0] - interval2[0];
}
});
- 插入新区间:
- 遍历排序后的
intervals
数组,对于每个区间,根据合并策略添加或更新列表中的区间。 - 同时,插入新区间
newInterval
,根据新区间与当前区间的相对位置,决定是否需要更新列表中的区间。
- 遍历排序后的
for (int i = 0; i < intervalsSize; ++i) {
int* interval = intervals[i];
if (interval[0] > right) {
// 在插入区间的右侧且无交集
if (!placed) {
int* tmp = malloc(sizeof(int) * 2);
tmp[0] = left, tmp[1] = right;
(*returnColumnSizes)[*returnSize] = 2;
ans[(*returnSize)++] = tmp;
placed = true;
}
int* tmp = malloc(sizeof(int) * 2);
memcpy(tmp, interval, sizeof(int) * 2);
(*returnColumnSizes)[*returnSize] = 2;
ans[(*returnSize)++] = tmp;
} else if (interval[1] < left) {
// 在插入区间的左侧且无交集
int* tmp = malloc(sizeof(int) * 2);
memcpy(tmp, interval, sizeof(int) * 2);
(*returnColumnSizes)[*returnSize] = 2;
ans[(*returnSize)++] = tmp;
} else {
// 与插入区间有交集,计算它们的并集
left = fmin(left, interval[0]);
right = fmax(right, interval[1]);
}
}
- 返回结果:
- 遍历完成后,将
List<int[]>
转换为二维数组并返回。
- 遍历完成后,将
return ans;
四、总结
通过上述步骤,我们能够有效地合并区间,并将新区间插入到区间列表中。关键在于正确地排序区间并合并它们。这种方法的时间复杂度为O(n log n),其中n是intervals
数组的长度,因为排序操作的时间复杂度为O(n log n)。空间复杂度为O(n),用于存储合并后的区间。
知识点精炼
一、核心概念
- 排序算法:在解决组合问题时,排序可以帮助我们找到最优解或近似解。
- 动态规划:在某些情况下,我们可以通过动态规划来优化算法,减少重复计算。
- 二维数组:在处理与位置相关的数据时,二维数组是一个非常有用的数据结构。
二、知识点精炼
-
区间合并问题:
- 给定一个二维数组
intervals
,其中每个子数组表示一个区间,需要合并这些区间,使得没有重叠的区间尽可能紧密相连。
- 给定一个二维数组
-
插入新区间:
- 创建一个
List<int[]>
,用于存储合并后的区间。 - 遍历排序后的
intervals
数组,对于每个区间,根据合并策略添加或更新列表中的区间。 - 同时,插入新区间
newInterval
,根据新区间与当前区间的相对位置,决定是否需要更新列表中的区间。
- 创建一个
-
返回结果:
- 遍历完成后,将
List<int[]>
转换为二维数组并返回。
- 遍历完成后,将
三、性能分析
- 时间复杂度:O(n log n),其中n是
intervals
数组的长度,因为排序操作的时间复杂度为O(n log n)。 - 空间复杂度:O(n),用于存储合并后的区间。
四、实际应用
- 数据处理:在处理与位置相关的数据时,这种算法可以帮助我们合并区间,使得没有重叠的区间尽可能紧密相连。
- 算法竞赛:在算法竞赛中,掌握这种算法对于解决与区间合并相关的问题非常有帮助。
五、代码实现要点
- 排序:正确使用
Arrays.sort
方法进行排序。 - 合并区间:正确实现合并策略,避免数组越界和重复添加。
- 返回结果:正确返回合并后的区间数组。
标签:tmp,returnSize,int,力扣,插入,intervals,第五十七,数组,区间 From: https://blog.csdn.net/m0_74932528/article/details/141069423