# Data Stream As Disjoint Intervals Problem

## Description

LeetCode Problem 352.

Given a data stream input of non-negative integers a_1, a_2, …, a_n, summarize the numbers seen so far as a list of disjoint intervals.

Implement the SummaryRanges class:

• SummaryRanges() Initializes the object with an empty stream.
• int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [start_i, end_i].

Example 1:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input
[[], [1], [], [3], [], [7], [], [2], [], [6], []]
Output
[null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]]
Explanation
SummaryRanges summaryRanges = new SummaryRanges();
summaryRanges.getIntervals(); // return [[1, 1]]
summaryRanges.addNum(3);      // arr = [1, 3]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3]]
summaryRanges.addNum(7);      // arr = [1, 3, 7]
summaryRanges.getIntervals(); // return [[1, 1], [3, 3], [7, 7]]
summaryRanges.addNum(2);      // arr = [1, 2, 3, 7]
summaryRanges.getIntervals(); // return [[1, 3], [7, 7]]
summaryRanges.addNum(6);      // arr = [1, 2, 3, 6, 7]
summaryRanges.getIntervals(); // return [[1, 3], [6, 7]]
``````

Constraints:

• 0 <= val <= 10^4
• At most 3 * 10^4 calls will be made to addNum and getIntervals.

## Sample C++ Code

For a new number n, find and return the index of interval [s, t] such that s is the largest ‘start’ that is smaller than n. If no such interval exists, return -1. This is done using binary search.

For example,

• new number 5, intervals [[1,1], [4,6], [8,8]], binary search returns 1.
• new number 0, intervals [[1,1], [4,6], [8,8]], binary search returns -1.

After we find this ‘index’, there are three circumstances:

• intervals[index] already contains val. Do nothing.
• val can be merged into intervals[index+1]. Modify intervals[index+1].start to val.
• val can be merged into intervals[index]. Modify intervals[index].end to val.
• val can’t be merged into either interval. Insert Interval( val, val).

Finally, after inserting val, we need to check whether intervals[index] and intervals[index+1] can be merged.

``````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
class SummaryRanges {
private:
vector<Interval> intervals = vector<Interval>();

int binarySearch(vector<Interval> intervals, int val) {
return binarySearchHelper(intervals, 0, intervals.size(), val);
}

int binarySearchHelper(vector<Interval> intervals, int start, int end, int val) {
if (start == end) return -1;
if (start+1 == end && intervals[start].start < val) return start;

int mid = (start + end)/2;
if (intervals[mid].start == val) {
return mid;
} else if (intervals[mid].start < val) {
return binarySearchHelper(intervals, mid, end, val);
} else { //intervals[mid] > val
return binarySearchHelper(intervals, start, mid, val);
}
}

public:
/** Initialize your data structure here. */
SummaryRanges() {

}

/** For a new number n, find the last(biggest) interval
*  [s,t], such that s < n. If no such interval exists,
*  return -1.
*/
int index = binarySearch(intervals, val);

// intervals[index] contains val
if (index != -1 && intervals[index].end >= val) {
return;
}

if (index != intervals.size()-1 && val + 1 == intervals[index+1].start) {
intervals[index+1].start = val;
} else if (index != -1 && val - 1 == intervals[index].end) {
intervals[index].end = val;
} else {
intervals.insert(intervals.begin() + index + 1, Interval(val, val));
}

//merge intervals[index] with intervals[index+1]
if (index != -1 && intervals[index].end + 1 == intervals[index+1].start) {
intervals[index].end = intervals[index+1].end;
intervals.erase(intervals.begin()+index+1);
}

return;
}

vector<Interval> getIntervals() {
return this->intervals;
}
};
``````