56. 合并區(qū)間
給出一個區(qū)間的集合逃贝，請合并所有重疊的區(qū)間。
示例 1:
輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出:[[1,6],[8,10],[15,18]]
解釋: 區(qū)間[1,3]和[2,6]重疊, 將它們合并為[1,6].
示例 2:
輸入: [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區(qū)間[1,4]和 [4,5] 可被視為重疊區(qū)間。
題解
可以被合并的區(qū)間一定是有交集的區(qū)間，前提是區(qū)間按照左端點排好序，這里的交集可以是一個點
只需要對所有的區(qū)間按照左端點升序排序，然后遍歷榜旦。
- 如果當前遍歷到的區(qū)間的左端點 > 結(jié)果集中最后一個區(qū)間的右端點，說明它們沒有交集景殷，此時把區(qū)間添加到結(jié)果集溅呢；
- 如果當前遍歷到的區(qū)間的左端點 <= 結(jié)果集中最后一個區(qū)間的右端點，說明它們有交集猿挚，此時產(chǎn)生合并操作咐旧，即：對結(jié)果集中最后一個區(qū)間的右端點更新（取兩個區(qū)間的最大值）
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;
public class Solution {
public int[][] merge(int[][] intervals) {
int len = intervals.length;
if (len < 2) {
return intervals;
}
// 按照起點排序
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
// 也可以使用 Stack，因為我們只關(guān)心結(jié)果集的最后一個區(qū)間
List<int[]> res = new ArrayList<>();
res.add(intervals[0]);
for (int i = 1; i < len; i++) {
int[] curInterval = intervals[i];
// 每次新遍歷到的列表與當前結(jié)果集中的最后一個區(qū)間的末尾端點進行比較
int[] peek = res.get(res.size() - 1);
if (curInterval[0] > peek[1]) {
res.add(curInterval);
} else {
// 注意绩蜻，這里應(yīng)該取最大
peek[1] = Math.max(curInterval[1], peek[1]);
}
}
return res.toArray(new int[res.size()][]);
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
int[][] res = solution.merge(intervals);
for (int i = 0; i < res.length; i++) {
System.out.println(Arrays.toString(res[i]));
}
}
}
復(fù)雜度分析：
- 時間復(fù)雜度：O(NlogN)铣墨，這里 N 是區(qū)間的長度；
- 空間復(fù)雜度：O(N)办绝，保存結(jié)果集需要的空間伊约，這里計算的是最壞情況，也就是所有的區(qū)間都沒有交點的時候
