57.Insert_Interval.md

57. Insert Interval

這題沒什麼特別的算法要處理，就是一個一個比較然後插入新的區間，所以會有幾個邊界條件要處理:

• 使用一個 result 來儲存最後的結果來處理這題會比較輕鬆

1. 先尋找是否有 Interval 的結尾比 newInterval 的開始還要小， 這代表這個 Interval 不會重疊可以直接加入 result
2. 尋找是否有 Interval 的開始比 newInterval 的結尾還要大
   • 這代表這個 Interval 會跟 newInterval 重疊，這時候可以比較兩者的開始與結尾，取最小的開始與最大的結尾
3. 都沒有 Interval 的開頭比 newInterval 的結尾還要大，這時候就可以把 newInterval 加入 result
4. 把剩下的 Interval 加入 result

Example:
這邊以 [[1,2],[3,5],[6,7],[8,10],[12,16]] 與 [4,8] 來舉例:

1. 先把 [1,2] 加入 result
2. 尋找重疊的 Interval
   • [3,5], [4,8] 重疊，取 [3,8]
   • [6,7], [3,8] 重疊，取 [3,8]
   • [8,10], [3,8] 重疊，取 [3,10]
3. [12,16] 跟 [3,10] 沒有重疊，把 [3,10] 加入 result
4. 把 [12,16] 加入 result
   • 結果為 [1,2],[3,10],[12,16]

Solution:

func insert(intervals [][]int, newInterval []int) [][]int {
	var result [][]int
	i := 0
	for i < len(intervals) && intervals[i][1] < newInterval[0] {
		result = append(result, intervals[i])
		i++
	}
	for i < len(intervals) && intervals[i][0] <= newInterval[1] {
		newInterval[0] = min(intervals[i][0], newInterval[0])
		newInterval[1] = max(intervals[i][1], newInterval[1])
		i++
	}
	result = append(result, newInterval)
	for i < len(intervals) {
		result = append(result, intervals[i])
		i++
	}

	return result
}

---

56. Merge Intervals

基本上在 traversal intervals 的時候跟 Insert 是一樣的邏輯:

1. 使用一個方法來固定 Left interval
2. 比較 Left interval 的結尾與 Right interval 的開始
   • L >= R 代表可以做合併
   • L < R 代表不用合併，需要移動 Left

Time Complexity O(nlogn) + O(n) = O(nlogn), Space Complexity O(n).

Solution:

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    result := [][]int{intervals[0]}
    for _, interval := range intervals {
        prev := result[len(result)-1]
        if interval[0] <= prev[1] {
            prev[1] = max(prev[1], interval[1])
        } else {
            result = append(result, interval)
        }
    }
    return result
}