Created
January 25, 2017 13:17
-
-
Save KirillLykov/44540dd12a250a974b4f98418ca57c4d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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 { | |
public: | |
struct Comp { | |
bool operator() (const Interval& l, const Interval& r) const { | |
return l.start < r.start; | |
} | |
}; | |
set< Interval, Comp > ds; | |
set< Interval, Comp >::iterator highBound(int val) { | |
return ds.upper_bound( Interval(val, val) ); | |
} | |
set< Interval, Comp >::iterator lowBound(int val) { | |
auto it = ds.lower_bound( Interval(val, val) ); | |
if (it == ds.begin()) | |
return ds.end(); | |
return --it; | |
} | |
/** Initialize your data structure here. */ | |
SummaryRanges() { | |
} | |
void addNum(int val) { | |
auto left = lowBound(val); | |
auto right = highBound(val); | |
Interval newInterval(val, val); | |
if (left != ds.end() && right != ds.end() && left->end + 1 == val && right->start == val + 1) { | |
newInterval.start = left->start; | |
newInterval.end = right->end; | |
ds.erase(left); | |
ds.erase(right); | |
} else if (left != ds.end() && left->end + 1 >= val) { | |
newInterval.start = left->start; | |
newInterval.end = max(left->end, val); | |
ds.erase(left); | |
} else if (right != ds.end() && right->start - 1 == val) { | |
newInterval.start = val; | |
newInterval.end = right->end; | |
ds.erase(right); | |
} | |
ds.insert( newInterval ); | |
} | |
vector<Interval> getIntervals() { | |
vector<Interval> res; | |
res.reserve(ds.size()); | |
for (auto e : ds) { | |
res.push_back(e); | |
} | |
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(); | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment