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.

Constraints:

• 1 <= intervals.length <= 104

• intervals[i].length == 2

• 0 <= starti <= endi <= 104

解題

Runtime: 16 ms, faster than 98.28%

Memory Usage: 6.9 MB, less than 64.73%

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
    
    res := make([][]int, 0)
    res = append(res, intervals[0])
    index := 0
    
    for i:=1; i<len(intervals); i++ {
        if res[index][1] >=  intervals[i][1] {
            continue
        }
        
        if res[index][1] >= intervals[i][0] && res[index][1] < intervals[i][1] {
            res[index] = []int{res[index][0], intervals[i][1]}
        } else {
            res = append(res, intervals[i])
            index++
        }
    }
    
    return res
}