-
Notifications
You must be signed in to change notification settings - Fork 0
/
56.merge-intervals.go
58 lines (51 loc) · 929 Bytes
/
56.merge-intervals.go
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
49
50
51
52
53
54
55
56
57
58
package solutions
import (
"sort"
)
/*
* @lc app=leetcode id=56 lang=golang
*
* [56] Merge Intervals
*/
/*
Your runtime beats 80.15 % of golang submissions
Your memory usage beats 61.34 % of golang submissions (6.9 MB)
*/
// @lc code=start
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 i := 1; i < len(intervals); i++ {
last := result[len(result)-1]
merged, ok := mergeAB(last, intervals[i])
if ok {
result[len(result)-1] = merged
} else {
result = append(result, intervals[i])
}
}
return result
}
func mergeAB(a, b []int) ([]int, bool) {
l := a
r := b
if a[0] > b[0] {
l = b
r = a
}
if l[1] < r[0] {
return nil, false
}
min := r[0]
if l[0] < r[0] {
min = l[0]
}
max := r[1]
if l[1] > r[1] {
max = l[1]
}
return []int{min, max}, true
}
// @lc code=end