Leetcode 56. 合并区间（排序会有意想不到的效果）

冷不防 2022-10-13 01:58 110阅读 0赞

#### 题目重述 ####

以数组 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  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 错误思路 ####

本题乍一看，实际上就是将重叠的区域覆盖，但是要注意的是，很容易跑偏的是，可能会想到打表，值可能是0或1，遍历一遍输入数据，将覆盖到的区域设置为1，最后在遍历一遍即可，但是这种方法只能过样例，不可以AC。  
例如：  
`[0,0][1,2]`这样的例子，如果按照上面的思路，会合并成\[0,2\] 但其实这样是错误的，按照本题的意思并不应该合并。

#### 正确思路 ####

*  观察不难发现，题目提供的是杂乱的，但如果我们对数据按组进行排序，那么在**排完序的列表**中，**合并的区间一定是连续的**
 *  基于上面条件，我们可对输入数据进行遍历，设定空列表A存储合并完成的列表，并考虑两种情况
 *  若当前遍历到的数据左端数据大于列表A最后一组数据的右端，说明是没有重合情况的，将这组数据直接add到列表A中即可
 *  否则说明右重合，更新列表A最后一组数据的右端值为 较远的右端点即可。

#### Java实现 ####

public int[][] merge(int[][] intervals) {
        
            // 先排序
            Arrays.sort(intervals, new Comparator<int[]>() {
        
                @Override
                public int compare(int[] o1, int[] o2) {
        
                    return o1[0] - o2[0];
                }
            });
            // 存储结果
            List<int[]> merged = new ArrayList<>();
            for (int i = 0; i <intervals.length ; i++) {
        
                int left = intervals[i][0];
                int right = intervals[i][1];
                // 不重合
                if(merged.isEmpty() || merged.get(merged.size()-1)[1]<left)
                {
        
                    // 直接添加
                    merged.add(new int[]{
        left,right});
                }else
                {
        
                    // 如果出现重合，更新右端点为最右端的
                    merged.get(merged.size()-1)[1] = Math.max(merged.get(merged.size()-1)[1],right);
                }
            }
            return merged.toArray(new int[merged.size()][]);
    
        }