Problem
You are given an array of non-overlapping intervals sorted by their start time, whereintervals[i] = [start, end].
You are also given a new interval
newInterval = [start, end]. Insert the new interval into the correct position and merge any overlapping intervals.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
intervals = [[1,3],[6,9]]
newInterval = [2,5]Output
[[1,5],[6,9]]Solution
This problem can be solved using a Greedy Approach.Since the intervals are already sorted by their start time, we can process them from left to right without sorting again.
There are three possible situations for every interval.
If the current interval ends before the new interval starts, there is no overlap, so we add the current interval to the result.
If the current interval starts after the new interval ends, there is no overlap and the new interval belongs before the current interval. We add the new interval to the result and then add all remaining intervals.
Otherwise, the current interval overlaps with the new interval. We merge them by updating the start and end boundaries of the new interval.
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int i = 0;
// Add intervals that end before the new interval starts.
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
result.add(intervals[i]);
i++;
}
// Merge all overlapping intervals.
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++;
}
// Add the merged interval.
result.add(newInterval);
// Add the remaining intervals.
while (i < intervals.length) {
result.add(intervals[i]);
i++;
}
return result.toArray(new int[0][]);
}
}
Complexity
Each interval is processed at most once, resulting inO(n) time complexity. The result list can contain up to n + 1 intervals, requiring O(n) space apart from the output.