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.
  • void addNum(int val) Adds the integer val to the 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
["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"]
[[], [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.addNum(1);      // arr = [1]
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.
     */
    void addNum(int val) {
        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;
    }
};




Related Posts

Data Stream As Disjoint Intervals Problem

LeetCode 352. Given a data stream input of non-negative integers...

Count Of Smaller Numbers After Self Problem

LeetCode 315. You are given an integer array nums and...

Count Complete Tree Nodes Problem

LeetCode 222. Given the root of a complete binary tree,...

Find Peak Element Problem

LeetCode 162. A peak element is an element that is...

Find Minimum In Rotated Sorted Array Problem

LeetCode 153. Suppose an array of length n sorted in...

Find Minimum In Rotated Sorted Array II Problem

LeetCode 154. Suppose an array of length n sorted in...