# Easy solution using one Set in C++, O(logN) for insert, but O(N) for getIntervals

• Actually I am looking for some O(1) for getInterval with O(logN) for add, but it looks not so straight-forward, and perhaps during a 45 minutes interview it will be so hard to code out. Using a set will be much easier to write the code.

``````set<int> tree; // binary search tree implemented by set, ordered
/** Initialize your data structure here. */
SummaryRanges() { }

void addNum(int val) {
tree.insert(val);
}

vector<Interval> getIntervals() {
// this will be about O(N), but very easy to get
vector<Interval> result;
bool isfirst = true;
int begin=0, end=0;

for(int i : tree) {
if(isfirst) {
begin = i;
end = i;
isfirst = false;
}
else {
if( i > end+1) {
result.push_back(Interval(begin, end));
begin = i;
end = i;
}
else {
end = i;
}
}
}

// for last one
result.push_back(Interval(begin, end));

return result;
}``````

• I think have a cleaner solution for the same complexity that you are trying to achieve:

``````class SummaryRanges {
set<int>st;
public:
void addNum(int val) {
st.insert(val);
}

vector<Interval> getIntervals() {
vector<Interval> result;
for (auto num : st) {
if (result.empty() || result.back().end + 1 != num)
result.emplace_back(num, num);
else
result.back().end = num;
}
return result;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.