合并区间

56. 合并区间

思路分析

• 对 vector<vector<int>> 排序，需要按照先比较区间开始，如果相同再比较区间结束，使用默认的排序规则即可
• 使用双指针，左边指针指向当前区间的开始
• 使用一个变量来记录连续的范围 t
• 右指针开始往后寻找，如果后续的区间的开始值比 t 还小，说明重复了，可以归并到一起
• 此时更新更大的结束值到 t
• 直到区间断开，将 t 作为区间结束，存储到答案里
• 然后移动左指针，跳过中间已经合并的区间

代码实现

java

class Solution {
    public static int[][] merge(int[][] intervals) {

        return merge_A(intervals);
    }

    public static int [][] merge_A(int [][]intervals){

        // 首先对二维数组，按照第一个元素进行排序
        Arrays.sort(intervals,new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                // 表示从小到大排序
                return o1[0] - o2[0];
            }
        });
        // 存放结果
        List<int[]> merge = new ArrayList();

        int t=0;
        for(int i=0;i<intervals.length;){
            int right = intervals[i][1];
            int j=i+1;
            while(j < intervals.length && right >= intervals[j][0]){
                // 记录当前区间的右侧
                right = Math.max(right,intervals[j][1]);
                j++;
            }

            merge.add(new int[]{intervals[i][0],right});
            i=j;
        }
        return merge.toArray(new int[merge.size()][]);
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {

        List<List<Integer>> list = new ArrayList();

        int sz = intervals.length;

        Arrays.sort(intervals,new Comparator<int[]>(){

            public int compare(int[]o1,int []o2){
                return o1[0]-o2[0];
            }
        });

        for(int i=0;i<sz;){

            int start = intervals[i][0];
            int temp = intervals[i][1];
            int idx = i+1;
            while(idx<sz && temp>=intervals[idx][0]){
                temp = Math.max(intervals[idx][1],temp);
                idx++;
            }
            ArrayList<Integer> ans =new ArrayList();
            ans.add(start);
            ans.add(temp);
            list.add(ans);
            i = idx;
        }
        int res[][] = new int[list.size()][2];
        for(int i=0;i<list.size();i++){
            res[i][0] = list.get(i).get(0);
            res[i][1] = list.get(i).get(1);
        }

        return res;

    }
}

​