Dare2Solve
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.
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:
current_start <= last_end
), merge them by updating the end of the last interval to the maximum of current_end
and last_end
.Return: The result list now contains non-overlapping intervals that cover all intervals in the input.
O(n log n) due to sorting, where n is the number of intervals. The merging process takes linear time O(n).
O(n) for storing the result list of intervals.
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
vector<vector<int>> 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;
}
};
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
import java.util.*;
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
List<int[]> 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()][]);
}
}
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;
};