0056. Merge Intervals (M)

佚名 4年前 (2020-07-04) 算法 620人围观抢沙发百度已收录

Merge Intervals (M)

题目

Given a collection of intervals, merge all overlapping intervals.

Example 1:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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.

题意

将给定数组中所有互相重叠的区间合并为一个大区间。

思路

将区间按照左端点值排序后进行处理。

代码实现

Java

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[][]{};
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        List<int[]> list = new ArrayList<>();
        int left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            int[] interval = intervals[i];
            if (left <= interval[1] && right >= interval[0]) {
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            } else {
                list.add(new int[]{left, right});
                left = interval[0];
                right = interval[1];
            }
        }
        list.add(new int[]{left, right});
        return list.toArray(new int[list.size()][]);
    }
}

JavaScript

var merge = function(intervals) {
    let ans = [];
    if (intervals.length == 0) {
        return ans;
    }
    intervals.sort((a, b) => a[0] - b[0]);
    let left = intervals[0][0], right = intervals[0][1];
    for (let interval of intervals) {
        if (left <= interval[1] && right >= interval[0]) {
            left = Math.min(left, interval[0]);
            right = Math.max(right, interval[1]);
        } else {
            ans.push([left, right]);
            left = interval[0];
            right = interval[1];
        }
    }
    ans.push([left, right]);
    return ans;
};