## Sunday, February 21, 2016

### Compress Number List II - AlgoBox by dietpepsi

Compress Number List II – AlgoBox by dietpepsi
Given a stream of positive integers, design a data structure supporting two operations:
1. void insert(int x) insert an element.
2. String toString() print out the integers in a compressed format.
The compressed format is like this, for example:
Given [8, 6, 4, 7]
Return "4, 6-8"

#### Method 1: BST

Using a balanced BST we could perform insertion, deletion and search in $O(\log n)$ time. The difference is for this problem we need to maintain intervals rather than numbers.
The trick is to use the start point as key and endpoint as value.

-- or we can just use binary index tree.

class DisjointIntervalTree {
private TreeMap<Integer, Integer> intervals = new TreeMap<>();
public void insert(int x) {
if (intervals.containsKey(x)) return;
Map.Entry<Integer, Integer> lower = intervals.lowerEntry(x);
if (lower != null && lower.getValue() >= x) return;
//try to merge intervals
int start = x, end = x;
Map.Entry<Integer, Integer> higher = intervals.higherEntry(x);
if (higher != null && higher.getKey() == x + 1) {
end = higher.getValue();
intervals.remove(x + 1);
}
if (lower != null && lower.getValue() == x - 1) {
start = lower.getKey();
intervals.remove(start);
}
intervals.put(start, end);
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (Map.Entry<Integer, Integer> interval : intervals.entrySet()) {
int start = interval.getKey();
int end = interval.getValue();
builder.append(start);
if (end > start)
builder.append("-").append(end);
builder.append(",");
}
builder.deleteCharAt(builder.length() - 1);
return builder.toString();
}
}