有关区间
# 有关区间
# lc56. 合并区间中等hot
题目描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
1
2
3
2
3
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
1
2
3
2
3
思路
没什么技巧就是暴力
var merge = function(intervals) {
if (!intervals || !intervals.length) return [];
intervals.sort((a, b) => a[0] - b[0]);
let ans = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
if (ans[ans.length - 1][1] >= intervals[i][0]) {
ans[ans.length - 1][1] = Math.max(ans[ans.length - 1][1], intervals[i][1])
} else {
ans.push(intervals[i])
}
}
return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
时间复杂度O(nlogn)
空间复杂度O(n)
# lc57. 插入区间中等
题目描述
给你一个 无重叠的 , 按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
1
2
2
示例 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] 重叠。
1
2
3
2
3
示例 3：
输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]
1
2
2
示例 4：
输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]
1
2
2
示例 5：
输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]
1
2
2
思路
还是常规暴力法
var insert = function(intervals, newInterval) {
let left = newInterval[0], right = newInterval[1]
let i = 0
while(i < intervals.length) {
if(newInterval[0] > intervals[i][1]) {
i++
continue
} else if(newInterval[1] < intervals[i][0]) {
break
} else {
left = Math.min(left, intervals[i][0])
right = Math.max(right, intervals[i][1])
intervals.splice(i, 1)
}
}
intervals.splice(i, 0, [left, right])
return intervals
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
时间复杂度:O(n)
空间复杂度:O(1)
上次更新: 2022/03/10, 14:51:31