352 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.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:

[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

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

Solution

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class SummaryRanges {
private:
    unordered_map<int, int> intervals;
    unordered_set<int> nums;
    struct comp {
        bool operator() (const Interval& i1, const Interval& i2 ) {
            return (i1.start<i2.start);
        }
    };
public:
    /** Initialize your data structure here. */
    SummaryRanges() {
    }

    void mergeUp(unordered_map<int, int>& intervals, int n1) {
        int lbd = n1 + intervals[n1];
        int ubd = n1+1 + intervals[n1+1];
        intervals.erase(intervals.find(n1));
        intervals.erase(intervals.find(n1+1));
        intervals[lbd] = ubd - lbd;
        intervals[ubd] = lbd - ubd;
        return;
    }
    void addNum(int val) {
        if ( nums.find(val) != nums.end() ) return;
        nums.insert(val);
        intervals[val] = 0;
        if ( intervals.find(val-1) != intervals.end() and intervals[val-1] <= 0 ) {
            mergeUp(intervals, val-1);
        }
        if ( intervals.find(val+1) != intervals.end() and intervals[val+1] >= 0 ) {
            mergeUp(intervals, val);
        }
        return;
    }

    vector<Interval> getIntervals() {
        vector<Interval> res;
        for (auto it = intervals.begin(); it != intervals.end(); it++ ) {
            if ( it->second < 0 ) continue;
            Interval newInt;
            newInt.start = it->first;
            newInt.end = it->first + it->second;
            res.push_back(newInt);
        }
        sort(res.begin(), res.end(), comp());
        return res;
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges obj = new SummaryRanges();
 * obj.addNum(val);
 * vector<Interval> param_2 = obj.getIntervals();
 */

Notes

How to overload sort in c++?

template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

• What is comp?

Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines. The function shall not modify any of its arguments. This can either be a function pointer or a function object.

• Example

// sort algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

struct myclass {
  bool operator() (int i,int j) { return (i<j);}
} myobject;

int main () {
  int myints[] = {32,71,12,45,26,80,53,33};
  std::vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33
  // using function as comp
  std::sort (myvector.begin(), myvector.end(), myfunction); 
  // using object as comp
  std::sort (myvector.begin(), myvector.end(), myobject); 
  return 0;
}