A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 352. Data Stream as Disjoint Intervals, the solution in this repository is mainly a data structure design solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: data structure design.
The notes already sitting in the source point us in the right direction:
- binary search
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are compareEnd, compareStart, operator, addNum.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//binary search
02//Runtime: 80 ms, faster than 99.62% of C++ online submissions for Data Stream as Disjoint Intervals.
03//Memory Usage: 31.1 MB, less than 100.00% of C++ online submissions for Data Stream as Disjoint Intervals.
04class SummaryRanges {
05public:
06 vector<vector<int>> intvls;
07
08// bool compareEnd(vector<int>& v1, vector<int>& v2){
09// return v1[1] < v2[1];
10// }
11
12// bool compareStart(vector<int>& v1, vector<int>& v2){
13// return v1[0] > v2[0];
14// }
15
16 //functors as argument to lower_bound and upper_bound
17 class compareEnd{
18 public:
19 compareEnd(){}
20 // bool operator() (vector<int>& v1, vector<int>& v2) const{
21 // return v1[1] < v2[1];
22 // }
23 // for lower_bound
24 bool operator() (vector<int>& v1, const int& v2) {
25 return v1[1] < v2;
26 }
27 };
28
29 class compareStart{
30 public:
31 compareStart(){}
32 // bool operator() (vector<int>& v1, vector<int>& v2) const{
33 // return v1[0] > v2[0];
34 // }
35 // for lower_bound
36 // bool operator() (vector<int>& v1, const int& v2) {
37 // return v1[0] < v2;
38 // }
39 //for upper_bound
40 bool operator() (const int& v1, vector<int>& v2) {
41 return v1 < v2[0];
42 }
43 };
44
45 compareEnd ce;
46 compareStart cs;
47
48 /** Initialize your data structure here. */
49 SummaryRanges() {
50
51 }
52
53 void addNum(int val) {
54 //find interval whose start > val
55 auto itStart = upper_bound(intvls.begin(), intvls.end(), val, cs);
56 //find interval whose start <= val
57 //https://stackoverflow.com/questions/9989731/algorithm-function-for-finding-last-item-less-than-or-equal-to-like-lower-bou
58 if(itStart != intvls.begin()) itStart = prev(itStart);
59 //find interval whose end >= val
60 auto itEnd = lower_bound(intvls.begin(), intvls.end(), val, ce);
61 int idxStart = itStart - intvls.begin();
62 int idxEnd = itEnd - intvls.begin();
63 // cout << "add " << val << endl;
64 // cout << "start: " << idxStart << ", end: " << idxEnd << endl;
65 if(itEnd == intvls.end()){
66 //val is larger than all intervals' end
67 // cout << "not found interval whose end >= " << val << endl;
68 if(idxEnd > 0 && intvls[idxEnd-1][1] + 1 == val){
69 //expand the interval before val
70 intvls[idxEnd-1][1] = val;
71 // cout << "expand end of last interval" << endl;
72 }else{
73 intvls.push_back({val, val});
74 // cout << "push back" << endl;
75 }
76 }else if(itStart == intvls.begin() && (*itStart)[0] > val){
77 //val is smaller than all intervals' start
78 // cout << "not found interval whose start <= " << val << endl;
79 if(val + 1 == intvls[idxEnd][0]){
80 //expand the interval before val
81 intvls[idxEnd][0] = val;
82 // cout << "expand start of next interval" << endl;
83 }else{
84 intvls.insert(intvls.begin(), {val, val});
85 // cout << "insert front" << endl;
86 }
87 }else if(itStart == itEnd && ((*itEnd)[1] >= val || (*itStart)[0] <= val)){
88 //val has been added, ignore
89 // cout << val << " already exists!" << endl;
90 }else{
91 bool combined = false;
92
93 if(idxStart >= 0 && intvls[idxStart][1] + 1 == val){
94 //expand the interval before val
95 intvls[idxStart][1] = val;
96 combined = true;
97 // cout << "expand end of last interval" << endl;
98 }
99
100 if(val+1 == intvls[idxEnd][0]){
101 //expand the interval after val
102 intvls[idxEnd][0] = val;
103 combined = true;
104 // cout << "expand start of next interval" << endl;
105 }
106
107 //if the surrounding intervals touch each other
108 if(combined && intvls[idxStart][1] >= intvls[idxEnd][0]){
109 //merge former interval with next interval
110 intvls[idxEnd][0] = intvls[idxStart][0];
111 intvls.erase(intvls.begin()+idxStart);
112 // cout << "merge last and next intervals, size: " << intvls.size() << endl;
113 }else if(!combined){
114 //val touch neither the boundaries of its surrounding interval
115 intvls.insert(itEnd, {val, val});
116 // cout << "not touch surrounding intervals, insert" << endl;
117 }
118 }
119 // cout << "===================" << endl;
120 }
121
122 vector<vector<int>> getIntervals() {
123 return intvls;
124 }
125};
126
127/**
128 * Your SummaryRanges object will be instantiated and called as such:
129 * SummaryRanges* obj = new SummaryRanges();
130 * obj->addNum(val);
131 * vector<vector<int>> param_2 = obj->getIntervals();
132 */Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.