Description
Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.
合并区间重叠/相邻的区间。
Solution
先对区间进行排序，然后逐个判断是否需要与前一个区间合并。
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
/**
* Definition for an interval.
* type Interval struct {
* Start int
* End int
* }
*/
type IntervalArr []Interval
func (h IntervalArr) Len() int {
return len(h)
}
func (h IntervalArr) Less(i, j int) bool {
return h[i].Start < h[j].Start
}
func (h IntervalArr) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func merge(intervals []Interval) []Interval {
if len(intervals) == 0 {
return nil
}
// 先对区间进行排序
sort.Sort(IntervalArr(intervals))
ret := make([]Interval, 0)
pInter := &intervals[0]
for i := 1; i < len(intervals); i++ {
curInter := &intervals[i]
if pInter.End >= curInter.Start {
if pInter.End < curInter.End {
// “合并操作”
pInter.End = curInter.End
}
} else {
ret = append(ret, *pInter)
pInter = curInter
}
}
ret = append(ret, *pInter)
return ret
}
|
Similar Problem
