贪心---合并区间 Posted on 2021-08-20 00:00:00 2021-08-20 00:00:00 by Author 摘要 给定若干个区间的集合,你能合并所有重叠的区间,并且返回一个不重叠区间的集合吗??? # 贪心---合并区间 1. 题目描述 - 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 - **提示：** - 1 <= intervals.length <= 104 - intervals[i].length == 2 - 0 <= starti <= endi <= 104 2. 示例描述 - 示例一 ```java 输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]。 ``` - 示例二 ```java 输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。 ``` 3. 解题思路 - 首先拿到本题，可以分析怎么使得多个重叠的区间连续排列在一起，这样就可以找到多个连续或者重叠区间的最小和最大值，那么就可以合并多个连续或者重叠的区间为一个区间。这里就需要排序，按照第一维度进行排序(也就是起始位置从小到大排序)，这就使得连续或者有重叠的区间都排列在一起了。 - 接下来就是怎么找到多个连续或者有重叠区间的最大值(前提是区间是连续或者有重叠时)，首先对于所给数组的第一个元素来说，起始位置就是第一个元素(区间)的起始点，终点位置就是第一个元素(区间)的终点位置，之后对数组其他元素(区间进行处理)如果该位置元素(区间)起始位置小于或者等于上个元素的终点位置，那么该区间需要与上个区间合并，如果该元素(区间)的开始位置大于上个区间的终点位置，说明上个区间已经合并完成了(即之后没有一个元素与上个已经合并的区间有重叠部分了),那么就记录上个合并区间的起始于终点位置，开启下个区间的合并，直到合并完整个数组，那么区间合并的任务也就完成了。 - 具体实现逻辑见如下代码，其实想法都很简单,如果自己动手操作一遍，那么印象会特别深刻的。 4. 代码示例 ```java public int[][] merge(int[][] intervals) { //如果所给的数组长度为0，直接返回null(考虑边界的条件） if(intervals.length<=0)return null; //定义一个存放结果集的数组集合 List<Integer> result = new ArrayList<>(); //对所给的数组进行第一维排序(按照从开始位置排序) Arrays.sort(intervals, new Comparator<int[]>() { public int compare(int[] interval1, int[] interval2) { return interval1[0] - interval2[0]; } }); //记录第一个区间的开始位置 int left = intervals[0][0]; //记录第一个区间的结束位置 int right = intervals[0][1]; //从数组第二个元素开始 for (int i = 1; i < intervals.length ; i++) { //如果区间有重叠(已经排序过了的) if(intervals[i][0]<=right){ //合并区间 right = Math.max(intervals[i][1],right); //继续向下找，看是否还有重叠区间 continue; }else { //如果该区间与上个区间没有重叠 //结果集合分别加入起始位置和区间的终点位置，那么一个区间就合并完成了 result.add(left); result.add(right); //同时下一个区间的起始与终点位置也要改变 left = intervals[i][0]; right = intervals[i][1]; } } //最后一次的区间还没有加入结果集合中 //那么最后一次的合并区间加入结果集合中 result.add(left); result.add(right); //然后把结果集合转化为数组形式 int n =result.size()/2; int res[][] = new int[n][2]; int k=0; //分别记录每个区间的开始位置与结束位置 for (int i = 0; i < result.size(); i++) { res[k][0] = result.get(i); res[k][1] = result.get(++i); k++; } //返回最终结果集 return res; } ```
{{ item.content }}
{{ child.content }}