Non-overlapping Intervals

Given a 2D array intervals[][] of representing 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.

Examples:

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, 3], [1, 3], [1, 3]]
Output: 2
Explanation: You need to remove two [1, 3] to make the rest of the intervals non-overlapping.

Input: intervals[][] = [[1, 2], [5, 10], [18, 35], [40, 45]]
Output: 0
Explanation: All ranges are already non overlapping.

Constraints:
1 ≤ intervals.size() ≤ 10⁵
|intervals_i| == 2
0 ≤ start_i < end_i <=5*10⁴

Approach 01:

class Solution {
 public:
  static int cmp(vector<int>& interval1, vector<int>& interval2) {
    return interval1[1] < interval2[1];
  }

  int minRemoval(vector<vector<int>>& intervals) {
    int numIntervals = intervals.size();
    int removalCount = 0;

    // Sort intervals by their end times using the comparator function
    sort(intervals.begin(), intervals.end(), cmp);

    int previousStart = intervals[0][0];
    int previousEnd = intervals[0][1];

    for (int i = 1; i < numIntervals; ++i) {
      if (intervals[i][0] < previousEnd) {
        removalCount++;
      } else {
        previousStart = intervals[i][0];
        previousEnd = intervals[i][1];
      }
    }

    return removalCount;
  }
};

class Solution:
    @staticmethod
    def cmp(interval1, interval2):
        return interval1[1] < interval2[1]

    def minRemoval(self, intervals):
        numIntervals = len(intervals)
        removalCount = 0

        # Sort intervals by their end times
        intervals.sort(key=lambda x: x[1])

        previousStart = intervals[0][0]
        previousEnd = intervals[0][1]

        for i in range(1, numIntervals):
            if intervals[i][0] < previousEnd:
                removalCount += 1
            else:
                previousStart = intervals[i][0]
                previousEnd = intervals[i][1]

        return removalCount

Time Complexity

• Sorting:
  • The intervals are sorted by their end times using the custom comparator function.
  • This step takes \(O(n \log n)\), where \(n\) is the number of intervals.
• Traversal:
  • The intervals are traversed once to determine the minimum number of removals.
  • This traversal takes \(O(n)\).
• Overall Time Complexity:

  The total time complexity is \(O(n \log n)\), dominated by the sorting step.

Space Complexity

• Sorting Auxiliary Space:
  • Sorting the intervals requires \(O(n)\) additional space, depending on the sorting algorithm used (e.g., mergesort or quicksort).
• Other Variables:
  • Variables like removalCount, previousStart, previousEnd, and loop variables require \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(n)\), dominated by the sorting auxiliary space.