56、合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
- $1 <= intervals.length <= 10^4$
intervals[i].length == 2- $0 <= start_i <= end_i <= 10^4$
思路 1
- 先排个序，构造数据类，定义比较器，调用系统排序方法
- 遍历一遍
- 如果最后一个元素与当前元素相交，合并区间，取最大的终点
- 如果不相交，作为一个新的区间加入到列表中
代码实现
$T_n = O(nlogn) S_n=O(1)$
面向对象编程。
class Solution {
// 设计区间类
class Interval{
public int start;
public int end;
public Interval(int s,int e){
this.start = s;
this.end = e;
}
public Interval(Interval i) {
this.start = i.start;
this.end = i.end;
}
}
// 自定义比较器
public class IntervalComparetor implements Comparator<Interval> {
@Override
public int compare(Interval a,Interval b) {
return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
}
}
// 合并算法
public List<Interval> merge(List<Interval> intervals) {
// 先排序
Collections.sort(intervals,new IntervalComparetor());
// 结果集合
LinkedList<Interval> res = new LinkedList<Interval>();
Interval interval = new Interval(intervals.get(0).start,intervals.get(0).end);
// 由于已经排好序，只要将后面的区间于合并好的最后一个区间进行比对就行了
for (Interval i : intervals) {
// 列表为空 或者 最后一个元素的终点小于当前区间的起点
if (res.isEmpty() || res.getLast().end < i.start) {
res.add(i);// 加入新的区间
} else {
// 更新最后一个区间的结束位置
res.getLast().end = Math.max(res.getLast().end,i.end);// 合并区间
}
}
return res;
}
public int[][] merge(int[][] intervals) {
int n = intervals.length;
// 特殊情况：只有一个区间或者没有区间
if (n == 1 || n == 0) {
return intervals;
}
// 数据转换
List<Interval> intervalList = new ArrayList<Interval>();
for (int i = 0;i < n;i++) {
intervalList.add(new Interval(intervals[i][0],intervals[i][1]));
}
// 调用处理合并函数
List<Interval> res = merge(intervalList);
// 结果数据处理
int[][] ans = new int[res.size()][2];
int k = 0;
for (Interval i : res) {
ans[k][0] = i.start;
ans[k][1] = i.end;
k++;
}
return ans;
}
}
直接操作原有数组
class Solution {
public int[][] merge(int[][] intervals) {
// 调用java 排序API，按照起始位置排序
Arrays.sort(intervals, (p, q) -> p[0] - q[0]);
int n = intervals.length;
int[][] ans = new int[n][2];
int last = 0;
for (int[] item : intervals) {
if(last > 0 && item[0] <= ans[last - 1][1]) {// 可以合并
if (item[1] > ans[last - 1][1]) {
ans[last - 1][1] = item[1];
}
// ans[last - 1][1] = Math.max(ans[last - 1][1], item[1]);
} else {
// 新增区间
ans[last][0] = item[0];
ans[last][1] = item[1];
last++;
}
}
// 构造结果
int[][] ansNew = new int[last][2];
int i = 0;
for(int[] item : ans) {
ansNew[i][0] = item[0];
ansNew[i][1] = item[1];
i++;
if (i == last) {
break;
}
}
return ansNew;
}
}
// 使用ArrayList存储新的区间对，然后再转成int[]
public class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (p, q) -> p[0] - q[0]); // 按照左端点从小到大排序
List<int[]> ans = new ArrayList<>();
for (int[] p : intervals) {
int m = ans.size();
if (m > 0 && p[0] <= ans.get(m - 1)[1]) { // 可以合并
ans.get(m - 1)[1] = Math.max(ans.get(m - 1)[1], p[1]); // 更新右端点最大值
} else { // 不相交，无法合并
ans.add(p); // 新的合并区间
}
}
return ans.toArray(new int[ans.size()][]);
}
}
57、插入区间
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 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] 重叠。
思路
- 遍历一边
- 未插入
- 找到出入位置
- 是否真的相交
- 不是真相交，按照大小依次加入到结果中
- 真的相交，合并，加入到结果中
- 加入标记为已插
- 是否真的相交
- 没有找到插入位置，将源列表中的元素加入到结果中
- 找到出入位置
- 已插入
- 将剩余元素依次合并到结果中
- 未插入
代码
class Solution {
// 区间类
class Interval{
public int start;
public int end;
public Interval(int s,int e){
this.start = s;
this.end = e;
}
public Interval(Interval i) {
this.start = i.start;
this.end = i.end;
}
public Interval merge(Interval i) {
this.start = Math.min(this.start,i.start);
this.end = Math.max(this.end,i.end);
return this;
}
}
public int[][] insert(int[][] intervals, int[] newInterval) {
int n = intervals.length;
LinkedList<Interval> res = new LinkedList<Interval>();// 结果列表
boolean isMerged = false;// 新节点已插入
if(n == 0) {
int[][] res1 = new int[1][2];
res1[0][0] = newInterval[0];
res1[0][1] = newInterval[1];
return res1;
}
for (int i = 0;i < n;i++) {
if (isMerged) {// 已合并
if (res.getLast().end < intervals[i][0]) {// 不相交
res.add(new Interval(intervals[i][0],intervals[i][1]));
}else {// 一定相交
// 合并
res.getLast().merge(new Interval(intervals[i][0],intervals[i][1]));
}
}else {// 未合并
if (newInterval[0] > intervals[i][1]) {// 不相交
res.add(new Interval(intervals[i][0],intervals[i][1]));
}else {// 可能相交
Interval t = new Interval(intervals[i][0],intervals[i][1]);
if (newInterval[1] >= intervals[i][0]) {
res.add(t.merge(new Interval(newInterval[0],newInterval[1])));
} else {
// 依次插入两个区间
res.add(new Interval(newInterval[0],newInterval[1]));
res.add(new Interval(intervals[i][0],intervals[i][1]));
}
isMerged = true;
}
}
}
if (!isMerged) {
res.add(new Interval(newInterval[0],newInterval[1]));
}
int[][] ans = new int[res.size()][2];
int k = 0;
for (Interval i : res) {
ans[k][0] = i.start;
ans[k][1] = i.end;
k++;
}
return ans;
}
}
// 1mm 代码
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> res = new ArrayList<>();
int cur = 0;
for(int[] interval : intervals){// 遍历
if(interval[1] < newInterval[0]){// 不可能相交
res.add(interval); // 加入结果
cur++;
}else if(newInterval[1] < interval[0]){// 不可能相交
res.add(interval);
}else{// 相交，更新结果
newInterval[0] = Math.min(interval[0],newInterval[0]);
newInterval[1] = Math.max(interval[1],newInterval[1]);
}
}
res.add(cur,newInterval);// 将合并的区间插入到结果的第cur位置
// 数据转换
int[][] intervalNew = new int[res.size()][2];
int index = 0;
for(int[] interval : res){
intervalNew[index++] = interval;
}
return intervalNew;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
