力扣hot100 合并区间 排序 贪心
Problem: 56. 合并区间
复杂度
时间复杂度: O ( n log n ) O(n\log{n}) O(nlogn)
空间复杂度: O ( n ) O(n) O(n)
Code
class Solution {
public int[][] merge(int[][] intervals)
{
Arrays.sort(intervals, (int[] a, int[] b) -> {
return a[0] - b[0];
});// 按照数组的第一个元素升序排序
int n = intervals.length;
int[][] res = new int[n][2];// 记录每个数组的左右边界
int idx = -1;
for (int[] a : intervals)
{
//第一个数组 或 当前数组不能融入 当前已有的数组 （左边界 > 已有数组的右边界）
if (idx == -1 || a[0] > res[idx][1])
res[++idx] = a;// 把当前数组 加入 结果
else
//可以融入的情况，右边界取较大值
res[idx][1] = Math.max(a[1], res[idx][1]);
}
//res数组经过合并区间，长度 <= n
return Arrays.copyOf(res, idx + 1);
}
}
原文地址：https://blog.csdn.net/lt6666678/article/details/135839120
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！