Problem
You are given an array of intervals, whereintervals[i] = [start, end] represents the start and end of an interval.
Merge all overlapping intervals and return an array containing only the non-overlapping intervals that cover all the intervals in the input.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
intervals = [[1,3],[2,6],[8,10],[15,18]]Output
[[1,6],[8,10],[15,18]]Solution
This problem can be solved using a Sorting approach.We first sort the intervals by their start time. This ensures that intervals that may overlap are processed next to each other.
We add the first interval to the result list and then process the remaining intervals one by one.
For each interval, we compare it with the last merged interval. If the current interval is completely contained within the last interval, there is nothing to change, so we skip it.
If the current interval overlaps with the last interval, we extend the end of the last interval to the current interval's end time.
Otherwise, the intervals do not overlap, so we add the current interval to the result list.
class Solution {
public int[][] merge(int[][] intervals) {
// Sort intervals by start time.
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> outList = new ArrayList<>();
// Add the first interval.
outList.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] lastInterval = outList.get(outList.size() - 1);
// Current interval is completely contained.
if (intervals[i][1] <= lastInterval[1]) {
continue;
}
// Current interval overlaps with the last interval.
if (intervals[i][0] <= lastInterval[1]) {
lastInterval[1] = intervals[i][1];
} else {
// No overlap, so add a new interval.
outList.add(intervals[i]);
}
}
return outList.toArray(new int[0][]);
}
}
Complexity
Sorting the intervals takesO(n log n) time, and traversing the intervals takes O(n) time, resulting in O(n log n) overall time complexity.
The output list can contain up to
n intervals, requiring O(n) space apart from the input array.