原题
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 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 {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> ans = new ArrayList<>();
int cur = 0;
boolean hasMerged = false;
while(cur<intervals.length){
if(!hasMerged && newInterval[0]<=intervals[cur][1]){
if(newInterval[1]<intervals[cur][0]){
ans.add(newInterval);
ans.add(intervals[cur]);
}
else{
int start = Math.min(newInterval[0],intervals[cur][0]);
while(cur<intervals.length&&newInterval[1]>=intervals[cur][0]){
cur++;
}
cur--;
ans.add(new int[]{start,Math.max(newInterval[1],intervals[cur][1])});
}
hasMerged = true;
}else ans.add(intervals[cur]);
cur++;
}
if(!hasMerged) ans.add(newInterval);
int[][] ansArray = new int[ans.size()][2];
for(int i = 0;i<ans.size();i++){
ansArray[i] = ans.get(i);
}
return ansArray;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode57-%e6%8f%92%e5%85%a5%e5%8c%ba%e9%97%b4/
