56. 合并区间(Medium)

题目描述

给出一个区间的集合，请合并所有重叠的区间。

样例

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

题解

区间问题，使用贪心法

视频解析：JS老毕

示例

Python 示例

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) < 2: return intervals
        intervals.sort(key = lambda x: x[0])
        ans = []
        cur = intervals[0]
        for interval in intervals:
            if interval[0] <= cur[1]:
                cur[1] = max(interval[1], cur[1])
            else:
                ans.append([cur[0], cur[1]])
                cur = interval
        ans.append(cur)
        return ans

Go 示例

func max(a, b int) int {
    if a > b { return a }
    return b
}

func merge(intervals [][]int) [][]int {
    n := len(intervals)
    if n < 2 { return intervals}
    sort.Slice(intervals, func(a, b int) bool {
        return intervals[a][0] < intervals[b][0]
    })
    cur := intervals[0]
    ans := make([][]int, 0)
    for _, interval := range intervals {
        if interval[0] <= cur[1] {
            cur[1] = max(cur[1], interval[1])
        } else {
            ans = append(ans, cur) 
            cur = interval
        }
    }
    ans = append(ans, cur)
    return ans 
}