算法篇12-LeetCode56. 合并区间

经典题目

56. 合并区间

我这里用的是比较简单的一种想法,就是先对数组按照区间的开始点排序,然后如果下一个点的开始点小于当前点的结束点,那这个区间就是可以合并的,这2个区间变成一个新的区间,开始点是小的点,结束点是大的点。

public int[][] merge(int[][] intervals) {
        /**
         *
         * 功能描述: 给出一个区间的集合,请合并所有重叠的区间。
         *
         * @param: [intervals]
         * @return: int[][]
         * @auther: smallfish
         * @date: 2020-03-25 21:28
         */
        int length = intervals.length;
        if (length == 0) {
            return new int[0][0];
        }
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        List<int[]> list = new ArrayList();
        int startX = intervals[0][0];
        int startY = intervals[0][1];
        for (int[] interval : intervals) {
            if (interval[0] <= startY) {
                startY = Math.max(interval[1], startY);
                startX = Math.min(interval[0], startX);
            } else {
                list.add(new int[]{startX, startY});
                startX = interval[0];
                startY = interval[1];
            }
        }
        list.add(new int[]{startX, startY});
        return list.toArray(new int[list.size()][]);
    }
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容