BiruLyu
5/26/2017 - 9:35 PM

## 352. Data Stream as Disjoint Intervals(ArrayList).java

/*

1. Use TreeSet guaranteed log(n) time cost for the basic operations (add, remove and contains).
The floor() method returns the greatest element in this set less than or equal to the given element,
or null if there is no such element.
The higher() method returns the least element in this set strictly greater than the given element,
or null if there is no such element.
Note: we use higher() instead of ceiling() to exclude the given element.

2. Use TreeMap
*/

/**
* 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; }
* }
*/
public class SummaryRanges {

TreeMap<Integer, Interval> tree;
/** Initialize your data structure here. */
public SummaryRanges() {
tree = new TreeMap<Integer, Interval>();
}

if(tree.containsKey(val)) return;

Integer low = tree.lowerKey(val);
Integer high = tree.higherKey(val);

if(low != null && high != null && tree.get(low).end + 1 == val && high == val + 1){
tree.get(low).end = tree.get(high).end;
tree.remove(high);
} else if (low != null && tree.get(low).end + 1 >= val){
tree.get(low).end = Math.max(tree.get(low).end, val);
} else if(high != null && high == val + 1) {
tree.put(val, new Interval(val, tree.get(high).end));
tree.remove(high);
} else {
tree.put(val, new Interval(val, val));
}
}

public List<Interval> getIntervals() {
return new ArrayList<>(tree.values());
}
}

/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();
* List<Interval> param_2 = obj.getIntervals();
*/
/**
* 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; }
* }
*/
public class SummaryRanges {
List<Interval> lst;
/** Initialize your data structure here. */
public SummaryRanges() {
lst = new ArrayList<Interval>();
}

int start = 0;
int end = lst.size() - 1;

if (lst.isEmpty()) {
return;
}

if (val < lst.get(start).start) {
if (val == lst.get(start).start - 1)
lst.get(start).start = val;
else
return;
}

if (val > lst.get(end).end) {
if (val == lst.get(end).end + 1)
lst.get(end).end = val;
else
return;
}

while (start < end - 1) {
int mid = (start + end) / 2;

if (val >= lst.get(mid).start && val <= lst.get(mid).end) {
return;
}

if (val > lst.get(mid).end) {
start = mid;
continue;
}

if (val < lst.get(mid).start) {
end = mid;
continue;
}
}

if (lst.get(start).end + 1 == val && lst.get(end).start - 1 == val) {
lst.get(start).end = lst.get(end).end;
lst.remove(end);
} else if (lst.get(start).end + 1 == val) {
lst.get(start).end = val;
} else if (lst.get(end).start - 1 == val) {
lst.get(end).start = val;
} else if (lst.get(start).start <= val && lst.get(start).end >= val) {
return;
} else if (lst.get(end).start <= val && lst.get(end).end >= val) {
return;
} else {
}
}

public List<Interval> getIntervals() {
return lst;
}
}

/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();