Learning Journal

2/10/2024

Non-overlapping Intervals

const START = 0,
  END = 1;

function eraseOverlapIntervals(intervals: number[][]): number {
  if (intervals.length <= 1) return 0;

  let first = 0,
    second = 1,
    count = 0;

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

  while (second < intervals.length) {
    if (intersect(intervals[first], intervals[second])) {
      if (intervals[first][END] < intervals[second][END]) {
        second++;
      } else {
        first = second;
        second++;
      }

      count++;
    } else {
      first = second;
      second++;
    }
  }

  return count;
}

function intersect(first: number[], second: number[]): boolean {
  return second[START] < first[END];
}const START = 0,
  END = 1;

function eraseOverlapIntervals(intervals: number[][]): number {
  if (intervals.length <= 1) return 0;

  let first = 0,
    second = 1,
    count = 0;

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

  while (second < intervals.length) {
    if (intersect(intervals[first], intervals[second])) {
      if (intervals[first][END] < intervals[second][END]) {
        second++;
      } else {
        first = second;
        second++;
      }

      count++;
    } else {
      first = second;
      second++;
    }
  }

  return count;
}

function intersect(first: number[], second: number[]): boolean {
  return second[START] < first[END];
}

THE PROBLEM

Here is how the algorithm works.

First, it sorts the intervals into ascending order of the starting point. Then, there are 2 pointers, first and second, that are set to the first and second interval initially.

Then, it goes over the intervals array; if the two intervals intersect, it will check to see which interval has the endpoint before the other, and it will keep that interval. Then, move to the next pair of intervals until it reaches the end.

This is a greedy algorithm. It is greedy in that it keep the shorter interval, because doing that way, we know that there will be more "space" left to get more intervals.

Revised by ChatGPT

This algorithm operates by first sorting the intervals in ascending order by their starting points. It then utilizes two pointers, first and second, initially set to the first two intervals, respectively.

The algorithm iterates through the array of intervals. If it encounters two intersection intervals, it determines which interval ends first. The strategy is to retain the interval with the earlier end point, thereby maximizing the remaining "space" to accommodate more intervals. This step is repeating for subsequent pairs of intervals until the end of the array is reached.

This approach is based on a greedy algorithm, characterized by its preference for keeping the interval that ends sooner. This choice is made under the assumption that it will allow for a greater number of non-overlapping intervals to be included.