-
-
Notifications
You must be signed in to change notification settings - Fork 5.6k
/
352. Data Stream as Disjoint Intervals.go
101 lines (88 loc) · 2.12 KB
/
352. Data Stream as Disjoint 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package leetcode
import (
"github.com/halfrost/LeetCode-Go/structures"
)
// Interval define
type Interval = structures.Interval
// SummaryRanges define
type SummaryRanges struct {
intervals []Interval
}
// Constructor352 define
func Constructor352() SummaryRanges {
return SummaryRanges{}
}
// AddNum define
func (sr *SummaryRanges) AddNum(val int) {
if sr.intervals == nil {
sr.intervals = []Interval{
{
Start: val,
End: val,
},
}
return
}
low, high := 0, len(sr.intervals)-1
for low <= high {
mid := low + (high-low)>>1
if sr.intervals[mid].Start <= val && val <= sr.intervals[mid].End {
return
} else if val < sr.intervals[mid].Start {
high = mid - 1
} else {
low = mid + 1
}
}
if low == 0 {
if sr.intervals[0].Start-1 == val {
sr.intervals[0].Start--
return
}
ni := Interval{Start: val, End: val}
sr.intervals = append(sr.intervals, ni)
copy(sr.intervals[1:], sr.intervals)
sr.intervals[0] = ni
return
}
if low == len(sr.intervals) {
if sr.intervals[low-1].End+1 == val {
sr.intervals[low-1].End++
return
}
sr.intervals = append(sr.intervals, Interval{Start: val, End: val})
return
}
if sr.intervals[low-1].End+1 < val && val < sr.intervals[low].Start-1 {
sr.intervals = append(sr.intervals, Interval{})
copy(sr.intervals[low+1:], sr.intervals[low:])
sr.intervals[low] = Interval{Start: val, End: val}
return
}
if sr.intervals[low-1].End == val-1 && val+1 == sr.intervals[low].Start {
sr.intervals[low-1].End = sr.intervals[low].End
n := len(sr.intervals)
copy(sr.intervals[low:], sr.intervals[low+1:])
sr.intervals = sr.intervals[:n-1]
return
}
if sr.intervals[low-1].End == val-1 {
sr.intervals[low-1].End++
} else {
sr.intervals[low].Start--
}
}
// GetIntervals define
func (sr *SummaryRanges) GetIntervals() [][]int {
intervals := [][]int{}
for _, interval := range sr.intervals {
intervals = append(intervals, []int{interval.Start, interval.End})
}
return intervals
}
/**
* Your SummaryRanges object will be instantiated and called as such:
* obj := Constructor();
* obj.AddNum(val);
* param_2 := obj.GetIntervals();
*/