-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
352.java
145 lines (124 loc) · 4.67 KB
/
352.java
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
__________________________________________________________________________________________________
sample 74 ms submission
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class SummaryRanges {
/** Initialize your data structure here. */
//List + simple binary search O(longN)
List<Interval> intervals;
public SummaryRanges() {
intervals = new ArrayList();
}
public void addNum(int val) {
// get idx to insert val, -1 if already exist in some interval
int idx = getIndex(val);
if (idx == -1) return;
Interval value = new Interval(val, val);
//check and merge left interval
if (idx > 0) {
Interval left = intervals.get(idx - 1);
if (val == left.end + 1) {
left.end = val;
value = left;
}
}
//check and merge right interval
if (idx < intervals.size()) {
Interval right = intervals.get(idx);
if (val == right.start - 1){
right.start = val;
value = right;
}
}
// check if val has merged with any adjacent intervals,
// if so check if adjecent intervals needs to be merged
if (!equal(value, new Interval(val, val))) {
Interval left = (idx > 0) ? intervals.get(idx - 1) : null;
Interval right = (idx < intervals.size()) ? intervals.get(idx) : null;
if (left != null && right != null && left.end == right.start) {
left.end = right.end;
intervals.remove(right);
}
}else {
intervals.add(idx, value);
}
}
public List<Interval> getIntervals() {
return intervals;
}
private int getIndex(int val) {
if (intervals.isEmpty()) return 0;
int start = 0, end = intervals.size();
while (start < end) {
int mid = start + (end-start) / 2;
Interval m = intervals.get(mid);
if (val >= m.start && val <= m.end) return -1;
else if (val > m.end) start = mid + 1;
else end = mid;
}
return end; // we can do "return start;" too
}
private boolean equal(Interval a, Interval b) {
return (a.start == b.start) && (a.end == b.end);
}
}
/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();
* obj.addNum(val);
* List<Interval> param_2 = obj.getIntervals();
*/
__________________________________________________________________________________________________
sample 41520 kb submission
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class SummaryRanges {
/** Initialize your data structure here. */
TreeSet<Interval> intervals;
public SummaryRanges() {
intervals = new TreeSet<>(Comparator.comparing(a->a.start));
}
public void addNum(int val) {
Interval higher = intervals.higher(new Interval(val, 0));//least interval among all intervals greater than (val, 0)
Interval lower = intervals.lower(new Interval(val, 0));
//If higher is not null, val < higher.start and hence val cannot be on interval higher and we already have a new val
//If lower is not null, val >lower.start and hence it is possible for val to be on interval lower, and we need to double check on it
if (lower != null && val >= lower.start && val <= lower.end) return;
// we check if the higher or lower need to be expanded if so
// we just remove them and add a new interval
int start = val, end = val;
if (higher != null && val == higher.start - 1) {
end = higher.end;
intervals.remove(higher);
}
if (lower != null && val == lower.end + 1) {
start = lower.start;
intervals.remove(lower);
}
intervals.add(new Interval(start, end));
}
public List<Interval> getIntervals() {
return new ArrayList(intervals);
}
}
/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();
* obj.addNum(val);
* List<Interval> param_2 = obj.getIntervals();
*/
__________________________________________________________________________________________________