56. Merge Intervals

难度: Medium

题目描述

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

 

Example 1:

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

Example 2:

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

Example 3:

Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: Intervals [1,4] and [4,7] are considered overlapping.

 

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

解题思路

代码实现

解决方案

java

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length < 2) {
            return intervals;
        }

        Arrays.sort(intervals, (a, b) -> {
            if (Integer.compare(a[0], b[0]) == 0) {
                return Integer.compare(a[1], b[1]);
            }
            return Integer.compare(a[0], b[0]);
        });

        int[][] res = new int[intervals.length][2];
        int index = 0;
        int left = intervals[0][0];
        int right = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] > right) {
                res[index][0] = left;
                res[index][1] = right;
                index++;
                left = intervals[i][0];
                right = intervals[i][1];

            } else if (intervals[i][0] <= right && intervals[i][1] >= right) {
                right = intervals[i][1];

            }
            if (i == intervals.length - 1) {
                res[index][0] = left;
                res[index][1] = right;
            }
        }

        return Arrays.copyOf(res, index + 1);

    }
}