Leetcode

Non-overlapping Intervals

  • Time:O(n\log n)
  • Space:O(1)

C++

class Solution {
 public:
  int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    if (intervals.empty())
      return 0;

    sort(begin(intervals), end(intervals),
         [](const auto& a, const auto& b) { return a[1] < b[1]; });

    int ans = 0;
    int currentEnd = intervals[0][1];

    for (int i = 1; i < intervals.size(); ++i)
      if (intervals[i][0] >= currentEnd)
        currentEnd = intervals[i][1];
      else
        ++ans;

    return ans;
  }
};

JAVA

class Solution {
  public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0)
      return 0;

    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

    int ans = 0;
    int currentEnd = intervals[0][1];

    for (int i = 1; i < intervals.length; ++i)
      if (intervals[i][0] >= currentEnd)
        currentEnd = intervals[i][1];
      else
        ++ans;

    return ans;
  }
}

Python

class Solution:
  def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    ans = 0
    currentEnd = -math.inf

    for interval in sorted(intervals, key=lambda x: x[1]):
      if interval[0] >= currentEnd:
        currentEnd = interval[1]
      else:
        ans += 1

    return ans