0435. Non-overlapping Intervals

leetcode

Problem Overview

The problem requires determining the minimum number of intervals to remove from a list of intervals so that the remaining intervals are non-overlapping.

Key Points:

Each interval is represented as a pair [start, end].
The goal is to minimize the number of intervals removed to ensure no two intervals overlap.

Solution Outline

Preferred Structure:
- Utilize sorting and greedy algorithms.
- Sort intervals based on their ending times.
Brute Force vs Optimal Solution:
- Brute Force Approach: Check all possible subsets of intervals to find the maximum non-overlapping subset. This is computationally expensive (exponential time complexity) and impractical for large inputs.
- Optimal Solution: Sort intervals by their end time and then use a greedy approach to select the maximum number of non-overlapping intervals.
Algorithm Choice:
- Greedy Algorithm: Sort intervals by their end times. Iterate through intervals, and for each interval, check if it overlaps with the last selected interval. If it doesn't, include it in the selection.
- This approach ensures a time complexity of O(n log n) due to sorting and a subsequent O(n) iteration.

Initial Skeleton of the Solution:

  /**
   * Function to find the minimum number of intervals to remove
   * to make the rest non-overlapping.
   * 
   * @param {number[][]} intervals - Array of intervals [start, end]
   * @returns {number} - Minimum number of intervals to remove
   */
  function eraseOverlapIntervals(intervals) {
      let erase = 0;
      for (let i = 0; i < intervals.length; i++) {
          let newIntervals = intervals.filter((el, idx) => idx !== i);
          // console.log("s" + JSON.stringify(newIntervals));
          if 
      }
      return 0;
  }

  function hasOverlapping(intervals) {
      for (let i = 0; i < intervals.length - 1; i++) {
          for (let n = i + 1; n < intervals.length; n++) {
              if(isOverlapping2(intervals[i]), intervals[n]) {
                  return true;
              }
          }
      }
      return false;
  }

  function isOverlapping2(interval1, interval2) {
    const [start1, end1] = interval1;
    const [start2, end2] = interval2;
    return !(end1 <= start2 || end2 <= start1);
}

  // Test cases
  const testCases = [
      { intervals: [[1, 2], [2, 3], [3, 4], [1, 3]], expected: 1 },
      // { intervals: [[1, 2], [1, 2], [1, 2]], expected: 2 },
      // { intervals: [[1, 2], [2, 3]], expected: 0 },
  ];

  testCases.forEach((test, index) => {
      const result = eraseOverlapIntervals(test.intervals);
      console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
  });