Today I have done leetcode's January LeetCoding Challenge with cpp.

January LeetCoding Challenge 28

Description

Data Stream as Disjoint Intervals

Given a data stream input of non-negative integers a1, a2, ..., an, 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 value) Adds the integer value to the stream.
• int[][] getIntervals() Returns a summary of the integers in the stream currently as a list of disjoint intervals [starti, endi]. The answer should be sorted by starti.

Example 1:

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 <= value <= 104
• At most 3 * 104 calls will be made to addNum and getIntervals.

Follow up: What if there are lots of merges and the number of disjoint intervals is small compared to the size of the data stream?

Solution

class SummaryRanges {
  vector<vector<int>> m;
public:
  void addNum(int val) {
    auto it = lower_bound(m.begin(), m.end(), vector<int>{val, val});
    int new_begin = val, new_end = val;
    if(it != m.begin() && ((*(--it))[1]+1 < val)) ++it;
    while(it != m.end() && val+1 >= (*it)[0] && val-1 <= (*it)[1]) {
      new_begin = min(new_begin, (*it)[0]);
      new_end = max(new_end, (*it)[1]);
      it = m.erase(it);
    }
    m.insert(it, vector<int> {new_begin, new_end});
  }
  
  vector<vector<int>> getIntervals() {
    vector<vector<int>> ans;
    for(auto &interval: m) {
      ans.push_back(interval);
    }
    return ans;
  }
};

// Accepted
// 9/9 cases passed (56 ms)
// Your runtime beats 92.94 % of cpp submissions
// Your memory usage beats 18.43 % of cpp submissions (34.3 MB)