LeetCode_区间问题_中等_56.合并区间

墨蓝 2023-10-06 18:41 61阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码操作（Java）

## 1.题目 ##

以数组 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 <= 104  
intervals\[i\].length == 2  
0 <= starti <= endi <= 104

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/merge-intervals

## 2.思路 ##

（1）排序

*  按照 intervals 中每个区间的左端点对所有区间进行升序排序；
 *  创建一个 ArrayList 对象 merged，并且其数组元素设置为区间，用于保存结果；
 *  开始遍历 intervals 中的每个区间，首先求出当前区间的左右端点值并分别赋值给 left 和 right，如果当前 merged 中还没有区间即merged.size() == 0，或者 merged 中最后一个区间 last 的右端点值 r 小于 left（r < left 说明当前区间与 last 没有交集），则直接将当前区间加入到 merged 中；否则需要更新 r，且 r 的值取 r 和 right 之间的最大值；
 *  遍历结束后，将 merged 中的区间存储到数组中再返回即可。

## 3.代码操作（Java） ##

//思路1————排序
    class Solution {
        
        public int[][] merge(int[][] intervals) {
        
            //按照 intervals 中每个区间的左端点进行升序排序
            Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
            List<int[]> res = new ArrayList<>();
            for (int[] interval : intervals) {
        
                //取出当前区间的左右端点
                int left = interval[0];
                int right = interval[1];
    			int size = res.size();
    			//获取 res 中最后一个区间的右端点，如果不存在则设为 -1
                int lastRight = size != 0 ? res.get(size - 1)[1] : -1;
                if (lastRight < left) {
        
                    res.add(interval);
                } else {
        
                    res.get(size - 1)[1] = Math.max(right, lastRight);
                }
            }
            return res.toArray(new int[res.size()][]);
        }
    }