56. 合并区间
查看题目中等
数组
高频
解法一：排序
时间复杂度：O(n log n) | 空间复杂度：O(n) | 推荐使用
动画演示
准备就绪 - 输入区间（用空格分隔，如：1,3 2,6 8,10 15,18），然后点击开始
合并步骤:
代码实现
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.ArrayList;
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) {
return new int[0][2];
}
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] interval1, int[] interval2) {
return interval1[0] - interval2[0];
}
});
List<int[]> merged = new ArrayList<int[]>();
for (int i = 0; i < intervals.length; ++i) {
int L = intervals[i][0], R = intervals[i][1];
if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
merged.add(new int[]{L, R});
} else {
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
}
}
return merged.toArray(new int[merged.size()][]);
}
}时间复杂度：O(n log n)
空间复杂度：O(n)
排序法：先将区间按起始位置排序，然后遍历排序后的区间，合并重叠的区间。