352. Data Stream as Disjoint Intervals

Well, I have to say the implementation of this problem depends. If there are many addNum() calls and only a few getIntervals() calls, we may want O(1) for addNum() and allows longer processing time for getIntervals(). The first implementation follows this idea.

1:  /**  
2:   * Definition for an interval.  
3:   * struct Interval {  
4:   *   int start;  
5:   *   int end;  
6:   *   Interval() : start(0), end(0) {}  
7:   *   Interval(int s, int e) : start(s), end(e) {}  
8:   * };  
9:   */  
10:  class SummaryRanges {  
11:  private:  
12:    vector<Interval> intervals;  
13:  public:  
14:    /** Initialize your data structure here. */  
15:    SummaryRanges() {  
16:    }  
17:    void addNum(int val) {  
18:      intervals.push_back(Interval(val, val));  
19:    }  
20:    vector<Interval> getIntervals() {  
21:      sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) { return a.start < b.start;});  
22:      for (int i = 1; i < intervals.size(); i++) {  
23:        if (intervals[i-1].end >= intervals[i].start-1) {  
24:          intervals[i-1].end = max(intervals[i-1].end, intervals[i].end);  
25:          intervals.erase(intervals.begin()+i);  
26:          i--;  
27:        }  
28:      }  
29:      return intervals;  
30:    }  
31:  };  
32:  /**  
33:   * Your SummaryRanges object will be instantiated and called as such:  
34:   * SummaryRanges obj = new SummaryRanges();  
35:   * obj.addNum(val);  
36:   * vector<Interval> param_2 = obj.getIntervals();  
37:   */    

On the other hand, if there are many getIntervals() calls but a few addNum() calls, we want O(1) for getIntervals() adn allows longer processing time for addNum(). The second implementation follows this way.

1:  /**  
2:   * Definition for an interval.  
3:   * struct Interval {  
4:   *   int start;  
5:   *   int end;  
6:   *   Interval() : start(0), end(0) {}  
7:   *   Interval(int s, int e) : start(s), end(e) {}  
8:   * };  
9:   */  
10:  class SummaryRanges {   
11:  private:   
12:    vector<Interval> intervals;  
13:  public:   
14:    void addNum(int val) {  
15:      vector<Interval>::iterator it = lower_bound(intervals.begin(), intervals.end(), Interval(val, val),   
16:                            [](Interval a, Interval b){ return a.start < b.start; });   
17:      intervals.insert(it, Interval(val, val));   
18:      for (int i = 1; i < intervals.size(); i++) {   
19:        if (intervals[i-1].end >= intervals[i].start-1) {   
20:          intervals[i-1].end = max(intervals[i-1].end, intervals[i].end);   
21:          intervals.erase(intervals.begin()+i);   
22:          i--;  
23:        }  
24:      }  
25:    }  
26:    vector<Interval> getIntervals() {  
27:      return intervals;  
28:    }   
29:  };  
30:  /**  
31:   * Your SummaryRanges object will be instantiated and called as such:  
32:   * SummaryRanges obj = new SummaryRanges();  
33:   * obj.addNum(val);  
34:   * vector<Interval> param_2 = obj.getIntervals();  
35:   */