/*
Note:
1. ⭐️代表newInterval之后的interval
if(newInterval == null || interval[1] < newInterval[0]) 中的 newInterval == null
2. ⭐️可能newInterval存在在最后一段
if(newInterval != null)
res.add(newInterval);
Explanation:
___: current interval(i); _ _ _: newInterval
1) i.end < newInterval.start,then we can safely add i to result;
newInterval still needs to be compared with latter intervals
|________|
|_ _ _ _ _|
2) i.start > newInterval.end,then we can safely add both to result,
and mark newInterval as null
|________|
|_ _ _ _ _|
3) There is overlap between i and newInterval. We can merge i into newInterval,
then use the updated newInterval to compare with latter intervals.
|________|
|_ _ _ _ _|
|________|
|_ _ _ _ _|
*/
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> res = new ArrayList<>();
for(int[] interval : intervals) {
if(newInterval == null || interval[1] < newInterval[0]) {
res.add(interval);
} else if(interval[0] > newInterval[1]) {
res.add(newInterval);
res.add(interval);
newInterval = null;
} else {
newInterval[0] = Math.min(interval[0], newInterval[0]);
newInterval[1] = Math.max(interval[1], newInterval[1]);
}
}
if(newInterval != null)
res.add(newInterval);
return res.toArray(new int[res.size()][]);
}
}
/*
1. add all the intervals ending before newInterval starts
2. merge all overlapping intervals to one considering newInterval
3. add all the intervals ending before newInterval
*/
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> res = new ArrayList<>();
int i = 0;
// add all the intervals ending before newInterval starts
while (i < intervals.length && intervals[i][1] < newInterval[0])
res.add(intervals[i++]);
// merge all overlapping intervals to one considering newInterval
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
res.add(newInterval);
// add all the intervals ending after newInterval
while (i < intervals.length)
res.add(intervals[i++]);
return res.toArray(new int[res.size()][]);
}
}