Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the ranges in the input. For example, given [[1,3],[2,6],[8,10],[15,18]], the output is [[1,6],[8,10],[15,18]] since [1,3] and [2,6] overlap.
Example
intervals = [[1,3], [2,6], [8,10], [15,18]]
Output: [[1,6], [8,10], [15,18]]
Intervals [1,3] and [2,6] overlap (they share the range 2-3), so they merge into [1,6]. The remaining intervals [8,10] and [15,18] don’t overlap with anything, so they stay as-is.
Sort all intervals by their start time. Walk through them one by one — if the current interval overlaps with the last merged interval (its start is less than or equal to the previous end), extend the end to cover both. Otherwise, the current interval stands on its own, so add it as a new entry.
Why this works
Once intervals are sorted by start time, any overlapping intervals must be next to each other. You walk through the sorted list and either extend the current merged interval (if there is overlap) or start a new one (if there is a gap). This single pass handles all possible overlaps including chains of multiple intervals merging together.
Step by step
- Sort by start time — this guarantees overlapping intervals are adjacent in the list.
- Start with the first interval — add it to the merged list as the initial entry.
- Compare each interval to the last merged one — if the current start is within the last interval’s range, extend the end.
- Otherwise start a new interval — no overlap means this interval is separate.
Time: O(n·log n)
Space: O(n)
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // sorting makes overlaps adjacent
List<int[]> merged = new ArrayList<>();
merged.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] last = merged.get(merged.size() - 1);
if (intervals[i][0] <= last[1]) { // overlaps with last merged interval
last[1] = Math.max(last[1], intervals[i][1]);
} else {
merged.add(intervals[i]);
}
}
return merged.toArray(new int[merged.size()][]);
}
}
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end()); // sorting makes overlaps adjacent
vector<vector<int>> merged = {intervals[0]};
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] <= merged.back()[1]) { // overlaps with last merged interval
merged.back()[1] = max(merged.back()[1], intervals[i][1]);
} else {
merged.push_back(intervals[i]);
}
}
return merged;
}
};
def merge(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0]) # sorting makes overlaps adjacent
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlaps with the last merged interval
merged[-1][1] = max(merged[-1][1], end) # extend to cover both
else:
merged.append([start, end])
return merged