LeetCode: 435 Erase Overlapping Intervals

LeetCode Problem: 435. Erase Overlapping Intervals

https://leetcode.com/problems/erase-overlapping-intervals/description/

Problem Description:

Given a collection of intervals, you need to remove the minimum number of intervals so that the remaining intervals do not overlap.

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

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0

Original Code (Greedy Approach):

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda pair: pair[0])  # Sort intervals by start time
        res = 0  # Initialize the count of intervals to remove
        pre_end = intervals[0][1]  # Initialize the end of the first interval

        for start, end in intervals[1:]:  # Iterate through intervals starting from the second
            if start >= pre_end:  # No overlap
                pre_end = end  # Update the end to the current interval's end
            else:  # Overlap exists
               res += 1  # Increment the count of removed intervals
               pre_end = min(pre_end, end)  # Update the end to the minimum of overlapping intervals

        return res  # Return the count of removed intervals

Line-by-Line Explanation and Example Execution:

1. class Solution:

   • Defines the Solution class.

2. def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:

   • Defines the method eraseOverlapIntervals which takes a list of intervals and returns the minimum number of intervals that need to be removed.

3. intervals.sort(key=lambda pair: pair[0])

   • Sorts the intervals by their start times to make it easier to check for overlaps.

4. res = 0

   • Initializes a counter res to keep track of the number of intervals that need to be removed.

5. pre_end = intervals[0][1]

   • Initializes pre_end to the end of the first interval.

6. for start, end in intervals[1:]:

   • Iterates over the sorted intervals starting from the second interval.

7. if start >= pre_end:

   • Checks if the current interval does not overlap with the previous one.

8. pre_end = end

   • If there is no overlap, updates pre_end to the end of the current interval.

9. else:

   • If there is an overlap, the code will execute the following:

     res += 1  # Increment the count of removed intervals
     pre_end = min(pre_end, end)  # Update the end to the minimum of overlapping intervals

10. return res

    • Returns the total count of intervals that need to be removed.

Example Execution:

Assuming we have the following input:

intervals = [[1,2],[2,3],[3,4],[1,3]]

1. Sorting:

   • The sorted intervals will be: [[1, 2], [1, 3], [2, 3], [3, 4]].

2. Initial State:

   • res = 0, pre_end = 2 (end of the first interval).

3. First Iteration:

   • Current interval: [1, 3]
   • Since 1 < 2, overlap exists:
     • Increment res to 1.
     • Update pre_end = min(2, 3) = 2.

4. Second Iteration:

   • Current interval: [2, 3]
   • Since 2 >= 2, no overlap:
     • Update pre_end to 3.

5. Third Iteration:

   • Current interval: [3, 4]
   • Since 3 >= 3, no overlap:
     • Update pre_end to 4.

6. Final Result:

   • The total intervals removed is 1.

Time Complexity Analysis:

• Time Complexity: O(n log n)
  • The sorting step dominates the time complexity, where n is the number of intervals.

Space Complexity Analysis:

• Space Complexity: O(1)
  • We only use a few variables, so the space complexity is constant.

Tips and Warnings:

1. Edge Cases:

   • Consider cases where the input list is empty or contains one interval.

2. Understanding Greedy Algorithms:

   • Ensure you understand the greedy approach of always keeping the interval with the smallest end time.

3. Interval Management:

   • Properly manage the end times of intervals to effectively determine overlaps.

Summary

• Greedy Method: Effectively counts the number of overlapping intervals to remove with a time complexity of O(n log n) and space complexity of O(1).
• Clear and Understandable: The code is straightforward and easy to follow, making it suitable for this type of problem.

Application Tips

1. Choose Appropriate Methods:

   • Select the method best suited to specific problem requirements to ensure efficiency and readability.

2. Handle Edge Cases:

   • Always consider edge cases in algorithm design to avoid potential errors.

3. Optimize Space Usage:

   • When handling large datasets, consider using space-efficient algorithms.