LeetCode 56. Merge Intervals

[Woodyiiiiiii]

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.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

---

这道题是数组区间合并问题。首先如何判断两个数组空间重叠呢——a[0] <= b[1] && a[1] >= b[0]。然后对重叠的数组取最小的左值，最大的右值，完成合并。

下面的方法时间复杂度是平方级别，空间复杂度是O(1)。其他方法可以去看LC的discussion板块。

class Solution {
    public int[][] merge(int[][] intervals) {
        int count = intervals.length; 

        for (int i = 0; i < intervals.length - 1; i++) {
            int[] currIntervals = intervals[i];

            for (int j = i + 1; j < intervals.length; j++) {
                int[] nextIntervals = intervals[j];

                if (overlap(currIntervals, nextIntervals)) {
                    intervals[j][0] = Math.min(currIntervals[0], nextIntervals[0]);
                    intervals[j][1] = Math.max(currIntervals[1], nextIntervals[1]);

                    intervals[i][0] = 0;
                    intervals[i][1] = -1;
                    count--;
                    break;
                }
            }
        }

        int[][] ans = new int[count][];

        for (int i = 0; i < intervals.length; i++) {
            if (intervals[i][0] <= intervals[i][1]) {
                ans[--count] = intervals[i];
            }
        }

        return ans;
    }

    private boolean overlap(int[] a, int[] b) {
        return a[0] <= b[1] && a[1] >= b[0];
    }
}

---

参考资料：

• https://leetcode.com/problems/merge-intervals/
• https://leetcode.com/problems/merge-intervals/discuss/685693/Java-simple-solution-1ms-100-O(1)-spacev