🎨Now live: Try our Free AI Image Generation Feature

Intuition
Given an array of intervals, the goal is to merge overlapping intervals to produce a list of non-overlapping intervals that cover all intervals in the input.
Approach
- Sorting: First, sort the intervals based on the starting value of each interval. This helps in easily identifying and merging overlapping intervals.
- Merging Intervals: Initialize an empty list to store merged intervals. Iterate through the sorted intervals:
- If the current interval overlaps with the last interval in the result list (i.e.,
current_start <= last_end
), merge them by updating the end of the last interval to the maximum ofcurrent_end
andlast_end
. - If there's no overlap, simply append the current interval to the result list. - Return: The result list now contains non-overlapping intervals that cover all intervals in the input.
Complexity
Time Complexity:
O(n log n) due to sorting, where n is the number of intervals. The merging process takes linear time O(n).
Space Complexity:
O(n) for storing the result list of intervals.
Code
C++
class Solution {
public:
vector> merge(vector>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector& a, const vector& b) {
return a[0] < b[0];
});
vector> res;
res.push_back({intervals[0][0], intervals[0][0]});
int lastIdx = 0;
for (const auto& interval : intervals) {
int s = interval[0];
int e = interval[1];
if (s <= res[lastIdx][1]) {
if (e > res[lastIdx][1]) {
res[lastIdx][1] = e;
}
} else {
res.push_back({s, e});
lastIdx++;
}
}
return res;
}
};
Python
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
result = []
result.append([intervals[0][0], intervals[0][1]])
lastIdx = 0
for interval in intervals:
s, e = interval
if s <= result[lastIdx][1]:
if e > result[lastIdx][1]:
result[lastIdx][1] = e
else:
result.append([s, e])
lastIdx += 1
return result
Java
import java.util.*;
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
List result = new ArrayList<>();
result.add(new int[] { intervals[0][0], intervals[0][0] });
int lastIdx = 0;
for (int[] interval : intervals) {
int s = interval[0];
int e = interval[1];
if (s <= result.get(lastIdx)[1]) {
if (e > result.get(lastIdx)[1]) {
result.get(lastIdx)[1] = e;
}
} else {
result.add(new int[] { s, e });
lastIdx++;
}
}
return result.toArray(new int[result.size()][]);
}
}
JavaScript
const merge = (intervals) => {
intervals = intervals.sort((a, b) => a[0] - b[0]);
let res = [[intervals[0][0], intervals[0][0]]];
let lastIdx = 0;
for (const [s, e] of intervals) {
if (s <= res[lastIdx][1]) {
if (e > res[lastIdx][1]) {
res[lastIdx][1] = e;
}
} else {
res.push([s, e]);
lastIdx++;
}
}
return res;
};