Simple C++ solution using vector with explanations

• ``````class SummaryRanges {
vector<Interval> _data;
public:
SummaryRanges() {

}

if (_data.empty()) { _data.push_back(Interval(val, val)); return; }

// find first interval which start is greater or equal to val
auto cmp = [](Interval a, Interval b) { return a.start < b.start; };
auto it = lower_bound(_data.begin(), _data.end(), Interval(val, val), cmp);

// we are only interested in found interval or one before it
// name them a and b. If it points to either begin or end of _data a and b will be the same
auto a = it == _data.begin() ? it : it - 1;
auto b = it == _data.end() ? it - 1 : it;

// if val is already there it must be in a or b. Nothing to do in that case
if (a->start <= val && a->end >= val) return;
if (b->start <= val && b->end >= val) return;

// val extends both intervals and they need to be merged
if (a->end + 1 == val && b->start - 1 == val) {
a->end = b->end;
_data.erase(b);
return;
}

// val extends a
if (a->end + 1 == val) { a->end = val; return; }

// val extends b
if (b->start - 1 == val) { b->start = val; return;}

// val extends no intervals in _data. Insert a new one
_data.insert(it, Interval(val, val));
}

vector<Interval> getIntervals() {
return _data;
}
};
``````

• excellent, it's brilliant

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