LeetCode.056.Merge Intervals 合并重叠区间

题目描述

56 Merge Intervals
https://leetcode-cn.com/problems/merge-intervals/

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

---

相似题目

LeetCode.836.Rectangle Overlap 矩形重叠
LeetCode.056.Merge Intervals 合并重叠区间
LeetCode.452.Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球

---

解题过程

按区间的左端点升序排序，则排序后可合并的重叠区间肯定是相邻聚集在一起的。然后从前往后遍历区间，每次尝试合并相邻的区间并放入结果集。

这题其实是一种贪心的策略，这种区间问题，一般都是贪心，做题多了看到就会想到用贪心，先排序

时间复杂度 O(nlogn)，空间复杂度 O(n)

代码写的复杂了，不需要转为 List 再排序，直接 Arrays.sort(intervals, Comparator.comparingInt(array -> array[0])); 即可

private static class SolutionV2020 {
    public int[][] merge(int[][] intervals) {
        if (null == intervals || intervals.length < 2) {
            return intervals;
        }
        List<Pair<Integer, Integer>> intervalList = new ArrayList<>();
        for (int[] interval : intervals) {
            intervalList.add(new Pair<>(interval[0], interval[1]));
        }
        // 按左端点排序
        Collections.sort(intervalList, (pair1, pair2) -> pair1.getKey() - pair2.getKey());

        List<Pair<Integer, Integer>> resList = new ArrayList<>();
        Pair<Integer, Integer> curInterval = intervalList.get(0);
        for (int i = 1; i < intervalList.size(); i++) {
            if (isIntersect(intervalList.get(i), curInterval)) {
                curInterval = mergeTwoInterval(intervalList.get(i), curInterval);
            } else {
                resList.add(curInterval);
                curInterval = intervalList.get(i);
            }
        }
        resList.add(curInterval);

        int[][] res = new int[resList.size()][2];
        for (int i = 0; i < resList.size(); i++) {
            int[] inter = new int[2];
            inter[0] = resList.get(i).getKey();
            inter[1] = resList.get(i).getValue();
            res[i] = inter;
        }

        return res;
    }

    // 判断两个区间是否有交点
    private boolean isIntersect(Pair<Integer, Integer> pair1, Pair<Integer, Integer> pair2) {
        return Math.max(pair1.getKey(), pair2.getKey()) <= Math.min(pair1.getValue(), pair2.getValue());
    }

    // 合并两个区间
    private Pair<Integer, Integer> mergeTwoInterval(Pair<Integer, Integer> pair1, Pair<Integer, Integer> pair2) {
        return new Pair<>(Math.min(pair1.getKey(), pair2.getKey()), Math.max(pair1.getValue(), pair2.getValue()));
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_056_MergeIntervals.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_056_MergeIntervals.java

---