刷题_56.合并区间

刷题LeetCode力扣数据结构与算法

一.题目描述：
以数组 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] 可被视为重叠区间。

二.解答

0      3
========  
            5       8
            =========
        ⇤    diff  ⇥
            ⇤  len ⇥

diff>len则没有交集
区间二的长度是8-5=3，区间二尾部为8，到区间1的尾部的距离是8-3=5,5>3,所以没有交集   


0      3
========  
    2       5
    =========

区间二的长度是5-2=3，区间二尾部为5，到区间1的尾部的距离是5-3=2,2<3,所以有交集   



0      3
========  
       3       5
        =========

区间二的长度是5-3=2，区间二尾部为5，到区间1的尾部的距离是5-3=2,2=2,交集就是3，有交集     




0      3
========  
  1  2
  ====

区间二的长度是2-1=1，区间二尾部为2，到区间1的尾部的距离是2-3=-1,-1<1,有交集 （这是diff小于0的情况）      

代码实现：

class Solution {
    public int[][] merge(int[][] intervals) {
            //将二维数组按照每个一维数组的左区间数从小到大排序好（这里我使用的是冒泡）
            sortArr(intervals);
            //一个个依次比较合并
            return myMerge(intervals);
    }

    public int[][] myMerge(int[][] sort) {
        for (int i = 0; i < sort.length-1; i++) {
            int len = sort[i+1][1] - sort[i+1][0];
            int diff = sort[i+1][1] - sort[i][1];
            //有交集
            if(len >= diff){
                if(diff < 0){
                    sort[i + 1] = sort[i];
                    sort[i] = null;
                }else {
                    sort[i + 1] = new int[]{sort[i][0], sort[i + 1][1]};
                    sort[i] = null;
                }
            }
        }
        List<int[]> collect = Arrays.stream(sort).filter(Objects::nonNull).collect(Collectors.toList());
        int[][] result = new int[collect.size()][2];
        for (int i = 0; i < collect.size(); i++) {
            result[i] = collect.get(i);
        }
        return result;
    }

    public int[][] sortArr(int[][] originArr){
        for (int i = 0; i < originArr.length-1; i++) {
            for (int j = 0; j < originArr.length-1-i; j++) {
                if(originArr[j][0] > originArr[j+1][0]){
                    int[] temp = originArr[j];
                    originArr[j] = originArr[j+1];
                    originArr[j+1] = temp;
                }
            }
        }
        return originArr;
    }

}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2021/05/17 00:16