未分類

Merge Intervals

Array, Go, LeetCode, Sort

Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example:

1
2
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
提示 解題應用
Array Array/Slice
Sort Interfaces實作

Default:

1
2
3
4
5
6
7
8
9
10
/**
 * Definition for an interval.
 * type Interval struct {
 *	   Start int
 *	   End   int
 * }
 */
func merge(intervals []Interval) []Interval {
}

解答思路:

這題最主要的關鍵在於排序，每組間隔的頭尾最好都能彼此做排序，先將每組的起頭做完排序，如果起頭的值相同則排序結尾的值，結果就會如同範例那樣井然有序，在每組間隔都能排序好的情況下，剩下的合併就會變的非常容易，一開始先前第一組間隔放入結果陣列中，接著才從第二組往下做判斷，如果前一組的結尾比下一組的開頭與結尾大，表示前一組完全包含了下一組的範圍便跳過，而如果是前一組的結尾比下一組的開頭大但比結尾小的話，此時就將下一組的結尾取代前一組(存於結果陣列中)的結尾，至於如果是前一組的結尾比下一組的開頭小，此時便直接將下一組插入結果陣列之中，最後合併完陣列間隔後才回傳結果。

程式碼解說:

因為在Golang 1.7中並沒有直接能排序struct資料陣列的library(1.8在sort中有)，所以就需要自行去實作一個interface並包含了三個method:Len(),Swap(),Less()，以利我們能直接用內建的sort來排序我們的struct資料陣列，基本上Len()與Swap()與一般型別陣列做法一致，至於Less則是要比較是否前者比較小，這邊就是內建sort在排序資料時所判斷的標準，因為我們的資料型別是struct且最好頭尾都能做排序，所以就改成如果兩個陣列元素struct的Start值相同就比較兩個陣個陣列元素struct的End值，否則便直接比較兩個陣列元素struct的Start值即可

1
2
3
4
5
6
7
8
9
type Sorter []Interval
func (a Sorter) Len() int      { return len(a) }
func (a Sorter) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a Sorter) Less(i, j int) bool {
	if a[i].Start == a[j].Start {
		return a[i].End < a[j].End
	}
	return a[i].Start < a[j].Start
}

再來就可以開始來處理參數所帶入的間隔陣列，如果間隔陣列為空便直接回傳該空的陣列，接著就是將間隔陣列用先前實作的interface來包裝以利我們的struct資料能根據Start與End來用內建的sort排序，排序結束後將間隔陣列的第一個間隔組放入結果陣列之中並紀錄該間隔的結尾值，之後利用迴圈從第二組間隔開始往下遍歷，如果先前紀錄的結尾比遍歷的開頭與結尾大，表示先前所紀錄的間隔範圍包含了此組間隔所以跳過，而如果先前紀錄的結尾比遍歷的開頭大但比結尾小的話，此時就將遍歷的結尾取代先前剛存於結果陣列中的間隔結尾，至於如果先前紀錄的結尾比遍歷的開頭小，則直接將遍歷的間隔組放入結果陣列之中，不管何種情況都要記得將紀錄的結尾值改成遍歷的結尾，最後合併完陣列間隔後才回傳結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func merge(intervals []Interval) []Interval {
	if len(intervals) == 0 {
		return intervals
	}
	sort.Sort(Sorter(intervals))
	result := []Interval{intervals[0]}
	curEnd := intervals[0].End
	for _, v := range intervals[1:] {
		if curEnd >= v.Start {
			if curEnd >= v.End {
				continue
			}
			result[len(result)-1].End = v.End
		} else {
			result = append(result, v)
		}
		curEnd = v.End
	}
	return result
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
type Sorter []Interval
func (a Sorter) Len() int      { return len(a) }
func (a Sorter) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a Sorter) Less(i, j int) bool {
	if a[i].Start == a[j].Start {
		return a[i].End < a[j].End
	}
	return a[i].Start < a[j].Start
}
func merge(intervals []Interval) []Interval {
	if len(intervals) == 0 {
		return intervals
	}
	sort.Sort(Sorter(intervals))
	result := []Interval{intervals[0]}
	curEnd := intervals[0].End
	for _, v := range intervals[1:] {
		if curEnd >= v.Start {
			if curEnd >= v.End {
				continue
			}
			result[len(result)-1].End = v.End
		} else {
			result = append(result, v)
		}
		curEnd = v.End
	}
	return result
}

總結:

一結構包含起始值與結尾值代表一個間隔範圍，如果有一結構陣列其每個元素分別代表不同間隔範圍，如果元素間的範圍有交集就要將其做合併，最後要回傳一合併後的結構陣列，最主要的關鍵在於每組間隔的頭尾最好都能彼此做排序，先將每組的起頭做完排序，如果起頭的值相同則排序結尾的值，結束後剩下的合併就會變的非常容易，一開始先前第一組間隔放入結果陣列中，接著才從第二組往下做判斷，如果前一組的結尾比下一組的開頭與結尾大，表示前一組完全包含了下一組的範圍便跳過，而如果是前一組的結尾比下一組的開頭大但比結尾小的話，此時就將下一組的結尾取代前一組(存於結果陣列中)的結尾，至於如果是前一組的結尾比下一組的開頭小，此時便直接將下一組插入結果陣列之中，最後合併完陣列間隔後才回傳結果。

分享到