Problem Statement
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Note that you don't need to modify intervals in-place. You can make a new array and return it.
Test Case
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Constraints
0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^5
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 10^5
Intuition
The given intervals array is already sorted and there are no overlapping intervals as of now. But the moment we insert the new interval, then it may cause some intervals to overlap.
So we need to start by adding all the intervals that won't cause any overlap. Then we will reach a point where the overlap might occur. Stop there and resolve the conflicts and add it to the result. Finally, the rest of the intervals will surely be non overlapping. Add it to the result array.
Approach
- Compare the endValue of current interval list and start value of new interval and add the non overlapping intervals to result.
- Resolve the overlapping by taking the min value for the start time and max value for the end time.
- Add the rest of the elements to the final array list.
Complexity
- Time complexity:
O(length of array)
- Space complexity:
O(1) if we do not consider the result array which we are returning at the end.
Code
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
if (intervals == null || intervals.length == 0) {
int [][] result = new int [1][2];
result[0][0] = newInterval[0];
result[0][1] = newInterval[1];
return result;
}
if (newInterval == null || newInterval.length == 0) {
return intervals;
}
int length = intervals.length;
List<int[]> resultList = new ArrayList<>();
int index = 0;
while (index < length && intervals[index][1] < newInterval[0]) {
resultList.add(intervals[index]);
index++;
}
while (index < length && intervals[index][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[index][0]);
newInterval[1] = Math.max(newInterval[1], intervals[index][1]);
index++;
}
resultList.add(newInterval);
while (index < length) {
resultList.add(intervals[index]);
index++;
}
return resultList.toArray(new int [0][]);
}
}