Leetcode 435 - Non-overlapping Intervals

Table of contents

Problem

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.

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 <= 10^5
• intervals[i].length == 2
• -5 * 10^4 <= starti < endi <= 5 * 10^4

Approaches

This problem aims to minimize the number of interval removals to prevent overlaps. We can achieve this efficiently using a greedy algorithm.

Greedy Algorithm:

• Sort Intervals: Sort the intervals based on their end times.
• Iterate and Compare: Iterate through the sorted intervals. If the current interval starts before the end of the previous interval, it’s overlapping, and we increment our removal count.
• Keep Track of Non-Overlapping End: Update the end time of the last non-overlapping interval for comparison in future iterations.

Solution: Greedy Algorithm

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        # Sort intervals based on their end time
        intervals.sort(key=lambda x: x[1])

        # Initialize the end time of the first interval
        end = intervals[0][1]
        count = 0

        # Iterate through the intervals
        for i in range(1, len(intervals)):
            if intervals[i][0] < end:
                # Increment count if overlapping
                count += 1
            else:
                # Update end time for next comparison
                end = intervals[i][1]

        return count

Time and Memory Complexity

The time complexity of this solution is O(n log n), primarily due to the sorting step, where n is the number of intervals. The space complexity is O(1), as we are only using a few extra variables for tracking.

Explanation

The key to this solution is sorting the intervals by their end time. This allows us to efficiently check for overlaps. If an interval starts before the end of the last non-overlapping interval, it’s overlapping, and we need to remove it. We keep updating the end time of the last non-overlapping interval for subsequent comparisons.

Visual Representation

Consider the input intervals = [[1,2],[2,3],[3,4],[1,3]].

1. Sorting:

   • Sorted Intervals: [[1,2], [1,3], [2,3], [3,4]].

2. Iteration and Comparison:

   • Start with [1,2], end time is 2.
   • Next is [1,3], starts before end of [1,2] (overlap), remove [1,3], increment count.
   • Then [2,3], no overlap with [1,2], update end to 3.
   • Finally [3,4], no overlap with [2,3].

3. Result:

   • One interval ([1,3]) was removed.

Intervals: [[1,2],[1,3],[2,3],[3,4]]
   |
   V
Sorted: [[1,2], [1,3], [2,3], [3,4]]
   |
   V
Remove [1,3] (overlap with [1,2])
   |
   V
Remaining: [[1,

2], [2,3], [3,4]]
   |
   V
Minimum Removals: 1

By applying this greedy strategy, we ensure the minimum number of intervals are removed to achieve non-overlapping intervals.