LeetCode 56: Merge Intervals (Sort + Greedy)
LeetCode 56SortingGreedyArrayToday we solve LeetCode 56 - Merge Intervals.
Source: https://leetcode.com/problems/merge-intervals/
English
Problem Summary
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 input ranges.
Key Insight
Sort intervals by start value first. Then scan from left to right and keep a result list:
- If current interval overlaps with the last merged interval, extend the end.
- Otherwise, append it as a new disjoint interval.
Brute Force and Why Insufficient
Trying to compare every pair repeatedly can degrade to O(n^2). Sorting once plus one pass is cleaner and optimal for this formulation.
Optimal Algorithm (Step-by-Step)
1) Sort by start ascending.
2) Initialize output with first interval.
3) For each next interval [s,e], compare with output tail [ls,le].
4) If s <= le, merge: tail becomes [ls, max(le,e)].
5) Else push as a new interval.
Complexity Analysis
Time: O(n log n) from sorting.
Space: O(n) for output (sorting may use extra stack/heap depending on implementation).
Common Pitfalls
- Forgetting to sort first.
- Using s < le instead of s <= le and missing boundary-touch merge.
- Modifying and appending in the wrong order, causing duplicates.
- Not handling empty input.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 0) return new int[0][0];
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
merged.add(new int[]{intervals[0][0], intervals[0][1]});
for (int i = 1; i < intervals.length; i++) {
int[] last = merged.get(merged.size() - 1);
int[] cur = intervals[i];
if (cur[0] <= last[1]) {
last[1] = Math.max(last[1], cur[1]);
} else {
merged.add(new int[]{cur[0], cur[1]});
}
}
return merged.toArray(new int[merged.size()][]);
}
}func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return [][]int{}
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
merged := [][]int{intervals[0]}
for i := 1; i < len(intervals); i++ {
last := merged[len(merged)-1]
cur := intervals[i]
if cur[0] <= last[1] {
if cur[1] > last[1] {
last[1] = cur[1]
}
} else {
merged = append(merged, cur)
}
}
return merged
}class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
merged.push_back(intervals[0]);
for (int i = 1; i < (int)intervals.size(); ++i) {
auto& last = merged.back();
auto& cur = intervals[i];
if (cur[0] <= last[1]) {
last[1] = max(last[1], cur[1]);
} else {
merged.push_back(cur);
}
}
return merged;
}
};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 s, e in intervals[1:]:
if s <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], e)
else:
merged.append([s, e])
return mergedvar merge = function(intervals) {
if (!intervals.length) return [];
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0].slice()];
for (let i = 1; i < intervals.length; i++) {
const last = merged[merged.length - 1];
const cur = intervals[i];
if (cur[0] <= last[1]) {
last[1] = Math.max(last[1], cur[1]);
} else {
merged.push(cur.slice());
}
}
return merged;
};中文
题目概述
给定若干区间 intervals[i] = [start_i, end_i]，请合并所有重叠区间，返回覆盖原始区间集合的最小不重叠区间数组。
核心思路
先按区间起点排序，再线性扫描维护“当前已合并区间尾部”：
- 若新区间与尾部重叠（s <= tailEnd），更新尾部右端点。
- 若不重叠，直接新增一个区间。
暴力解法与不足
反复两两比较与重排可能达到 O(n^2)，实现复杂且不稳定。排序后单次扫描更稳妥。
最优算法（步骤）
1）按起点升序排序。
2）结果集先放入第一个区间。
3）逐个读取下一个区间，与结果集尾部比较。
4）若重叠则尾部右端点取最大值。
5）若不重叠则直接加入结果集。
复杂度分析
时间复杂度：O(n log n)（排序主导）。
空间复杂度：O(n)（结果集；排序额外空间视语言实现而定）。
常见陷阱
- 忘记排序。
- 把重叠条件写成 s < tailEnd，漏掉端点相接情况。
- 直接复用引用导致结果被后续覆盖。
- 空数组输入未处理。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 0) return new int[0][0];
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
merged.add(new int[]{intervals[0][0], intervals[0][1]});
for (int i = 1; i < intervals.length; i++) {
int[] last = merged.get(merged.size() - 1);
int[] cur = intervals[i];
if (cur[0] <= last[1]) {
last[1] = Math.max(last[1], cur[1]);
} else {
merged.add(new int[]{cur[0], cur[1]});
}
}
return merged.toArray(new int[merged.size()][]);
}
}func merge(intervals [][]int) [][]int {
if len(intervals) == 0 {
return [][]int{}
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
merged := [][]int{intervals[0]}
for i := 1; i < len(intervals); i++ {
last := merged[len(merged)-1]
cur := intervals[i]
if cur[0] <= last[1] {
if cur[1] > last[1] {
last[1] = cur[1]
}
} else {
merged = append(merged, cur)
}
}
return merged
}class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
merged.push_back(intervals[0]);
for (int i = 1; i < (int)intervals.size(); ++i) {
auto& last = merged.back();
auto& cur = intervals[i];
if (cur[0] <= last[1]) {
last[1] = max(last[1], cur[1]);
} else {
merged.push_back(cur);
}
}
return merged;
}
};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 s, e in intervals[1:]:
if s <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], e)
else:
merged.append([s, e])
return mergedvar merge = function(intervals) {
if (!intervals.length) return [];
intervals.sort((a, b) => a[0] - b[0]);
const merged = [intervals[0].slice()];
for (let i = 1; i < intervals.length; i++) {
const last = merged[merged.length - 1];
const cur = intervals[i];
if (cur[0] <= last[1]) {
last[1] = Math.max(last[1], cur[1]);
} else {
merged.push(cur.slice());
}
}
return merged;
};
Comments