今天的題目要秋將所有重疊的區間合併並回傳一個非重疊區間的陣列，而且其回傳的陣列必須覆蓋到輸入中的所有區間。

問題

https://leetcode.com/problems/merge-intervals/

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

提示

Python

在 Python 可以利用 list1.sort(key=myFun) 透過自己定義的 Function 對陣列作排序．

def myFun(n):
  return abs(n)

list1 = [2, -4, 0, -1, 3, 9]
list1.sort(key=myFun)
print(list1)    # [0, -1, 2, 3, -4, 9]

list2 = [("Brandon", 100), ("Lia", 85), ("John", 60)]
list2.sort(key=lambda x: x[1])
print(list2)    # [('John', 60), ('Lia', 85), ('Brandon', 100)]

Python 可以利用 max() 跟 min() 來取得兩個數值或一個陣列間，最大及最小值．

>>> max(3, 6)
6
>>> min(3, 6)
3
>>> max([1, 3, -2])
3
>>> min([1, 3, -2])
-2

Go

Go 可以利用 sort 套件裡面的 Slice() 跟 SliceStable() 函式來做客製化的排序．

例如：

package main

import (
	"fmt"
	"sort"
)

func main() {
	// Sorting a slice of strings by length
	fruits := []string{"Apple", "Mongo", "Pineapple"}
	sort.SliceStable(fruits, func(i, j int) bool {
		return len(fruits[i]) < len(fruits[j])
	})
	fmt.Println("Sorted strings by length: ", strs)
}

Go 可以利用 math 套件裡面的 func Max(x, y float64) float64 and func Min(x, y float64) float64 函式來取的兩個變數中較大及較小的值
但變數只能是 "Float64" 格式的資料, Int 格式的變數要先轉成 "Float64" 格式才可以使用 . 而且也不像 Python 那樣可以接受陣列當變數，找出陣列中最大或最小值．

package main

import (
	"fmt"
	"math"
)

func main() {
	a := 5
	b := 3
	c := math.Max(float64(a), float64(b))
	fmt.Println(c)
}

我的答案

先把陣列裡的區段根據他們的開始值排序，然後對每個區段，如果該區段的起始值比前一個區段的結束值小，則合併．

Python

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        intervals.sort(key=lambda x: x[0])

        merged = []
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                # if the list of merged intervals is empty or if the current
                # interval does not overlap with the previous, simply append it.
                merged.append(interval)
            else:
                # otherwise, there is overlap, so we merge the current and previous
                # intervals.
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

Go

import (
    "fmt"
    "sort"
    "math"
)

func merge(intervals [][]int) [][]int {
    sort.SliceStable(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
    //fmt.Println(intervals)
    
    merged := [][]int{}
    for _, interval := range intervals {
        //fmt.Println(interval)
        l := len(merged)
        if l == 0 || merged[l-1][1] < interval[0] {
            merged = append(merged, interval)
        } else {
            merged[l-1][1] = int(math.Max(float64(merged[l-1][1]), float64(interval[1])))
        }
    }
    return merged
}