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.

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.

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.

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;

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

let prevEnd = intervals[0][1];

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

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

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

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.

Eda Eren

LeetCode Meditations: Non-overlapping Intervals

Time and space complexity