56.合并区间.md

56. 合并区间

url

题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

方法

code

js

let merge = intervals => {
    if (intervals === null || intervals.length <= 1) return intervals;
    intervals.sort((a, b) => {
        return a[0] - b[0]
    });
    let list = []
    let i = 0, n = intervals.length;
    while (i < n) {
        let l = intervals[i][0];
        let r = intervals[i][1];
        while (i < n - 1 && r >= intervals[i + 1][0]) {
            r = Math.max(r, intervals[i + 1][1])
            i++;
        }
        list.push([l, r]);
        i++;
    }
    return list;
}

go

type numsSortable [][]int

func (nums numsSortable) Len() int {
	return len(nums)
}
func (nums numsSortable) Less(i, j int) bool {
	return nums[i][0] <= nums[j][0]
}
func (nums numsSortable) Swap(i, j int) {
	nums[i], nums[j] = nums[j], nums[i]
}
func merge2(intervals [][]int) [][]int {
	Max := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	if len(intervals) <= 1{
		return intervals
	}
	sort.Sort(numsSortable(intervals))
	list := make([][]int, 0)
	i, n := 0, len(intervals)
	for i < n {
		l, r := intervals[i][0], intervals[i][1]
		for i < n-1 && r >= intervals[i+1][0] {
			r = Max(r, intervals[i + 1][1])
			i++
		}
		list = append(list, []int{l, r})
		i++
	}
	return list
}

java

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) return intervals;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> list = new ArrayList<>();
        int i = 0;
        int n = intervals.length;
        while (i < n) {
            int l = intervals[i][0];
            int r = intervals[i][1];
            while (i < n - 1 && r >= intervals[i + 1][0]) {
                r = Math.max(r, intervals[i + 1][1]);
                i++;
            }
            list.add(new int[] {l, r});
            i++;
        }
        return list.toArray(new int[list.size()][2]);
    }
}