Non-overlapping Intervals

---

Non-overlapping Intervals: Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of
the intervals are non-overlapping.

---

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make
the rest of the intervals non-overlapping.

---

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of
the intervals since they're already non-overlapping.

---

Constraints:

• 1 <= intervals.length <= 10^5
• intervals[i].length == 2
• -5 * 10^4 <= start_i < end_i <= 5 * 10^4

---

Try this Problem on your own or check similar problems:

1. Determine if Two Events Have Conflict
2. Minimum Number of Arrows to Burst Balloons

Solution:

Java

public int eraseOverlapIntervals(int[][] intervals) {
    if(intervals.length == 1) return 0;
    Arrays.sort(intervals, (a,b) -> a[1] - b[1]);

    int end = intervals[0][1];
    int numberOfNonOverlapping = 1;

    for(int i = 1; i < intervals.length; ++i){
        if(intervals[i][0] >= end) {
          end = intervals[i][1];
          ++numberOfNonOverlapping;
        }
    }
    return intervals.length - numberOfNonOverlapping;
}

JavaScript

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function (intervals) {
  if (intervals.length === 1) return 0;
  intervals.sort((a, b) => a[1] - b[1]);

  let end = intervals[0][1];
  let numberOfNonOverlapping = 1;

  for (let i = 1; i < intervals.length; ++i) {
    if (intervals[i][0] >= end) {
      end = intervals[i][1];
      ++numberOfNonOverlapping;
    }
  }
  return intervals.length - numberOfNonOverlapping;
};

Python

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) == 1:
            return 0
        intervals.sort(key=lambda x: x[1])

        end = intervals[0][1]
        numberOfNonOverlapping = 1

        for i in range(1, len(intervals)):
            if intervals[i][0] >= end:
                end = intervals[i][1]
                numberOfNonOverlapping += 1
        return len(intervals) - numberOfNonOverlapping

C++

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 1)
            return 0;
        std::sort(intervals.begin(), intervals.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
            return a[1] < b[1];
        });

        int end = intervals[0][1];
        int numberOfNonOverlapping = 1;

        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0] >= end) {
                end = intervals[i][1];
                ++numberOfNonOverlapping;
            }
        }
        return intervals.size() - numberOfNonOverlapping;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(nlogn)
• Space Complexity: O(1)

---

Explanation:

The problem can be reframed to find the number of intervals which are not overlapping, and we would get the final number of overlapping by just subtracting the number of non-overlapping from the total number of intervals. So how do we get the number of non-overlapping intervals? We first sort the input array of intervals by end time. Why end time? The interval with early start could be long, so the intervals that end fast make space for other intervals to be put after them. Each time we iterate over the next interval in the list we check if its start is after our currently chosen interval's end, if it is, that means they're not overlapping, and we increase the number of non-overlapping intervals while also choosing the new interval as our selected one. Time complexity is equal to complexity taken to sort the list of intervals of length n.