LeetCode Meditations: Non-overlapping Intervals

The description for Non-overlapping Intervals is:

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.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

For example:

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.

Or:

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.

Or:

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.

---

For this problem, NeetCode has a great solution that starts with sorting the intervals, as we did in the previous problem.
We can also initialize a variable to keep track of the number of removals.

intervals.sort((a, b) => a[0] - b[0]);

let numRemovals = 0;

Now that our intervals are sorted, we'll go through each one, checking whether they overlap or not. We'll keep track of the previous interval's end for that, so let's initialize a prevEnd variable that initially holds the first interval's end:

let prevEnd = intervals[0][1];

Note
For two intervals not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

In this problem, when the end of an interval is equal to the other's start, they are considered non-overlapping.

So, here we can say that two intervals will overlap if the start of one is strictly less than the end of the other. In that case, we'll update prevEnd to be the lesser value of the two ends so that we have a less chance of overlapping with the next interval. Otherwise, we'll continue as before:

for (let i = 1; i < intervals.length; i++) {
  // overlapping, update the previous end
  // (remove the interval with the larger end value 
  // so we have less chance of overlapping with the next one)
  if (intervals[i][0] < prevEnd) {
    numRemovals++;
    prevEnd = Math.min(prevEnd, intervals[i][1]);
  } else {
    prevEnd = intervals[i][1];
  }
}

Finally, we can return numRemovals:

function eraseOverlapIntervals(intervals: number[][]): number {
  /* ... */

  return numRemovals;
}

And, the final solution we have looks like this:

function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);

  let numRemovals = 0;
  let prevEnd = intervals[0][1];

  for (let i = 1; i < intervals.length; i++) {
    // overlapping, update the previous end
    // remove the interval with the larger end value so we have less chance of overlapping with the next one
    if (intervals[i][0] < prevEnd) {
      numRemovals++;
      prevEnd = Math.min(prevEnd, intervals[i][1]);
    } else {
      prevEnd = intervals[i][1];
    }
  }

  return numRemovals;
}

Time and space complexity

Since we sort the intervals at the start, the time complexity will be $O(n \ log \ n)$ . We don't have an additional data structure whose size will increase as the input size increases, so the space complexity is $O(1)$ .

---

Next up, we will start the last chapter of the series, Bit Manipulation. Until then, happy coding.