{x}
blog image

Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], 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.

 

Example 1:

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.

Example 2:

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.

Example 3:

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.

 

Constraints:

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104

Solution Explanation for Non-overlapping Intervals

The problem asks for the minimum number of intervals to remove from a given set of intervals such that the remaining intervals do not overlap. The optimal solution leverages a greedy approach combined with sorting.

Approach

The core idea is to sort the intervals by their end times. After sorting, we iterate through the intervals, keeping track of the latest non-overlapping interval's end time. If the current interval's start time is greater than or equal to the latest end time, it means the current interval doesn't overlap with the previously selected intervals, and we can add it to the set of non-overlapping intervals. Otherwise, the current interval overlaps, and we increment the counter of removed intervals.

Why this works:

Sorting by end time ensures that we prioritize intervals that finish early. By selecting the interval with the earliest end time at each step, we maximize the chances of fitting more non-overlapping intervals. This greedy strategy guarantees finding the minimum number of intervals to remove.

Time and Space Complexity Analysis

Time Complexity: O(N log N), dominated by the sorting step where N is the number of intervals. The iteration through the sorted intervals takes linear time.

Space Complexity: O(1). The algorithm uses a constant amount of extra space irrespective of the input size. We only need a few variables to track the current end time and the count of removed intervals.

Code Implementation Details (Python3 as Example)

The Python code efficiently implements this greedy approach:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1]) # Sort by end times
        ans, t = 0, intervals[0][1] # Initialize: ans (removed count), t (last end time)
        for s, e in intervals[1:]: # Iterate from the second interval
            if s >= t: # Non-overlapping
                t = e # Update last end time
            else: # Overlapping
                ans += 1 # Increment removed count
        return ans

The code first sorts the intervals list using a lambda function as the key to sort based on the second element (end time) of each interval. Then it initializes ans (the count of intervals to remove) to 0 and t (the end time of the last non-overlapping interval) to the end time of the first interval. It iterates through the sorted intervals starting from the second interval. If the current interval's start time (s) is greater than or equal to the last end time (t), it means there's no overlap, so we update t with the current interval's end time (e). Otherwise, if there's an overlap, we increment ans. Finally, it returns the value of ans.

Other languages (Java, C++, Go, TypeScript) implement the same logic with minor syntax variations to accommodate their respective features. The core algorithm remains consistent across all implementations.