LeetCode 精选 TOP 面试题（Java 实现）—— 合并区间

一、题目描述

1.1 题目

• 合并区间

• 给出一个区间的集合，请合并所有重叠的区间。

• 示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

• 示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

1.2 知识点

• 排序
• 数组

1.3 题目链接

• https://leetcode-cn.com/problems/merge-intervals/

二、解题思路

2.1 自研思路

  这道题需要考虑的因素比较多，主要是 数组是否有序 、对于包含区间的处理 以及 尾区间的处理 等。首先对于数组是否有序的问题，因为题中没有说明数组有序，即可能出现 [[1,4],[0,3]] 这种情况，因此我们首先要先将数组进行排序，使数组中的区间按 x 的升序排列，上述数组排序完后为 [[0,3],[1,4]] 。

  为了对数组进行合并，我们首先要遍历数组，并在遍历的过程中对区间进行合并。首先进行合并是将前区间合并至当前下标区间（即判断一个区间是否需要被合并，需要在其下一个区间处理时进行判断），首先判断当前区间的 x 是否大于上个区间的 y ，如果大于则说明当前区间是一个独立的区间，所以上个区间可以进行合并。合并的具体过程就是将之前记录的合并区间 x 和 y 更新至已合并区间的末尾处（该末尾由单独的指针 rear 进行维护）。合并完成后递增 rear 指针，然后将合并区间的 x 更新为当前区间的 x 。之后判断当前区间的 y 是否大于合并区间的 y ，如果大于则更新合并区间的 y 。如果刚刚已经合并过，则此时是必大于的，所以一定会更新。而如果在刚刚的判断中，当前区间的 x 小于等于合并区间的 y ，如 [[1,3],[2,4]]，则此时不更新合并区间的 x ，而应更新合并区间的 y 为当前区间的 y ，相当于进行了区间合并操作 [[1,4]] 。

  需要注意的是，因为我们每一个区间的合并保存操作都是在其下一个区间处理时完成的，因此最后应单独对数组的尾区间进行处理，以及将原数组中合并后的区间拷贝到新的结果数组中。

三、实现代码

3.1 自研实现

class Solution {

    public int[][] merge(int[][] intervals) {
        
        if(intervals.length == 0 || intervals.length == 1) 
        	return intervals;

		// 数组排序
        Comparator cmp = new MyComparator();
        Arrays.sort(intervals, cmp);

        int left = intervals[0][0], right = intervals[0][1], rear = 0;
        for(int i = 1; i < intervals.length; i++) {

            if(intervals[i][0] > right){
                intervals[rear][0] = left;
                intervals[rear][1] = right;
                rear++;

                left = intervals[i][0];
            }
            right = intervals[i][1] > right ? intervals[i][1] : right; // [[1,4],[2,3]]
        }
        
        // 单独处理尾区间
        intervals[rear][0] = left;
        intervals[rear][1] = right;     

		// 拷贝结果
        int[][] res = new int[rear+1][2];
        for(int i = 0; i < rear+1; i++)
            res[i] = intervals[i];

        return res;
    }

    class MyComparator implements Comparator<int[]>{
    	@Override
    	    public int compare(int[] o1, int[] o2) {
    		    return o1[0]-o2[0];    
            }
    }
}