Merge Intervals
Merge Intervals
Problem Statement
Given a collection of intervals, merge all overlapping intervals.
Video Explanation
Approach
To merge the intervals, we can first sort them based on the start time. Then, we can iterate through the sorted intervals and merge them as needed.
Steps:
-
Initialize : Sort:
- Sort the intervals by their start times.
- Initialize a list to hold the merged intervals.
-
Iterate:
- For each interval, check if it overlaps with the last merged interval.
- If it does, merge them. If not, add the interval to the list.
-
Return:
- Return the merged intervals.
Solutions
- C++
- Java
- Python
- JavaScript
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (const auto& interval : intervals) {
if (merged.empty() || merged.back()[1] < interval[0]) {
merged.push_back(interval);
} else {
merged.back()[1] = max(merged.back()[1], interval[1]);
}
}
return merged;
}
};
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) return intervals;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> result = new ArrayList<>();
int[] current = intervals[0];
result.add(current);
for (int[] interval : intervals) {
if (interval[0] <= current[1]) {
current[1] = Math.max(current[1], interval[1]);
} else {
current = interval;
result.add(current);
}
}
return result.toArray(new int[result.size()][]);
}
}
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for i in range(1, len(intervals)):
current = intervals[i]
last_merged = merged[-1]
if current[0] <= last_merged[1]:
last_merged[1] = max(last_merged[1], current[1])
else:
merged.append(current)
return merged
var merge = function(intervals) {
if (!intervals.length) return [];
intervals.sort((a, b) => a[0] - b[0]);
const res = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const curr = intervals[i];
const last = res[res.length - 1];
if (curr[0] <= last[1]) {
last[1] = Math.max(last[1], curr[1]);
} else {
res.push(curr);
}
}
return res;
};
Track Your Progress
Done with this topic? Mark it as complete to track your progress.
💬 Discuss this page
Have a question or spot something confusing in "Merge Intervals"? Ask below — it's backed by GitHub Discussions, so maintainers get notified like any other GitHub activity.