题目
解题思路
- 根据区间的起始点对区间进行排序
- 排序后对交叉区间进行合并,添加新的间隔区间
- 当前区间只需要考虑与上一个存储区间的关系
代码展示
class Solution {
public int[][] merge(int[][] intervals) {
if(intervals.length == 0) return intervals;
Map<Integer,Integer> data = new TreeMap<>();
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
data.put(intervals[0][0],intervals[0][1]);
int before = intervals[0][0];
for (int i = 1; i < intervals.length; i++){
if (intervals[i][0] > data.get(before)){
before = intervals[i][0];
data.put(intervals[i][0], intervals[i][1]);
} else {
data.put(before, Math.max(data.get(before), intervals[i][1]));
}
}
int[][] ans = new int[data.size()][2];
int index = 0;
for (Integer num : data.keySet()){
ans[index][0] = num;
ans[index++][1] = data.get(num);
}
return ans;
}
}