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


  • 0

    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;
        }
    

Log in to reply
 

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