LeetCode ---- 56、合并区间

  • 时间:
  • 来源:互联网
  • 文章标签:

题目链接

思路:

首先给数组排序,排序时按照每个数组的第一个元素升序排序,这样在后面合并的时候就会很方便。

合并时,若当前数组的区间与之前的数组的区间属于交集关系或者包含关系,则需要将其合并。

例如:[ 1, 4 ]  [3, 5] 合并后为 [1, 5]

    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0) {
            return intervals;
        }
        /**
         * Arrays.sort(intervals, new Comparator<int[]>() {
         *             public int compare(int[] a, int[] b) {
         *                 return a[0] - b[0];
         *             }
         *         });
         */
        // java8的简化写法,可以替代上面注释部分
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

        List<int[]> list = new ArrayList<>();
        list.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            // 拿到前一个区间
            int[] peek = list.get(list.size() - 1);
            // 若前一个区间的右边界比当前区间的左边界大,则需要合并,合并时注意右边界如何选择
            if (peek[1] >= intervals[i][0]) {
                peek[1] = peek[1] > intervals[i][1] ? peek[1] : intervals[i][1];
            } else {   // 不需要合并
                list.add(intervals[i]);
            }
        }
        return list.toArray(new int[list.size()][]);
    }

 

本文链接http://www.taodudu.cc/news/show-83102.html