云南网站建设运营,wordpress视频调整方向,互动网站建设多少钱,网站分享大家好#xff01;我是曾续缘#x1f4ab; 今天是《LeetCode 热题 100》系列 发车第 14 天 普通数组第 2 题 ❤️点赞 #x1f44d; 收藏 ⭐再看#xff0c;养成习惯 合并区间 以数组 intervals 表示若干个区间的集合#xff0c;其中单个区间为 intervals[i] [starti, en… 大家好我是曾续缘 今天是《LeetCode 热题 100》系列 发车第 14 天 普通数组第 2 题 ❤️点赞 收藏 ⭐再看养成习惯 合并区间 以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。 示例 1 输入intervals [[1,3],[2,6],[8,10],[15,18]]
输出[[1,6],[8,10],[15,18]]
解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2 输入intervals [[1,4],[4,5]]
输出[[1,5]]
解释区间 [1,4] 和 [4,5] 可被视为重叠区间。 提示 1 intervals.length 104intervals[i].length 20 starti endi 104 难度 解题方法
我们将列表中的区间按照左端点升序排序,这样可以从左到右遍历添加区间, 这样保证了我们答案的区间也是按照左端点升序排序的,
假设我们遍历到位置i使用l,r记录当前遍历到的区间的左右端点,取出我们答案中最靠右的区间, 因为答案中的区间已经是不重叠的了当前区间只有可能和最靠右的区间重叠。判断当前区间是否和答案中最靠右的区间有交集,如果无交集, 说明不用合并, 将当前区间添加到答案中.如果有交集, 由于左端点升序排序答案区间的左端点肯定小于当前区间的左端点,新区间的左端点就是答案区间的左端点如果答案区间不包含当前区间, 合并区间就相当于延长答案区间的右端点.如果答案区间包含当前区间新区间的右端点就是答案的右端点不用变。
Code
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, new Comparatorint[](){public int compare(int[] a1, int[] a2){return a1[0] - a2[0];}});Listint[] ans new ArrayListint[]();for(int i 0; i intervals.length; i){int l intervals[i][0], r intervals[i][1];if(ans.size() 0 || ans.get(ans.size() - 1)[1] l){ans.add(new int[]{l, r});}else{ans.get(ans.size() - 1)[1] Math.max(ans.get(ans.size() - 1)[1], r);}}return ans.toArray(new int[ans.size()][]);}
}
