# 6-line C++ O(N logN) concise solution, concept of pair-wise overlapping group (detailed explanation)

• Key observation: if we have a group of pair-wise overlapping intervals, we can only keep exactly one of them remaining.

But the question is which one to keep? Well, apparently, we want to keep the interval from the group with minimum end point `minEnd` so it has least chance to overlap with any next coming intervals to the right. Therefore, the algorithm is straightforward:

• Sort given intervals by start points;
• For each interval, check its start point vs `minEnd`:
• if `interval.start >= minEnd`, it means no intervals need to be removed since the current interval wouldn't overlap with any previous intervals if previous intervals in pair-wise overlapping group are removed except the one with end as `minEnd`;
• otherwise, the current interval will become of those in the pair-wise overlapping group, and we need to increment removal count by one and update `minEnd` as well.
``````    int eraseOverlapIntervals(vector<Interval>& its) {
sort(its.begin(), its.end(), [](Interval& x, Interval& y){return x.start<y.start;});
int res = 0, minEnd = INT_MIN; // min end of pair-wise overlapping group
for (auto it : its) {
if (it.start >= minEnd) minEnd = it.end; // no overlap
else ++res, minEnd = min(minEnd, it.end); // overlap and update count and minEnd
}
return res;
}
``````

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