algoadvance

Leetcode Problem 435: Non-overlapping Intervals

Given an array of 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.

Example:

• Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
• Output: 1

• Explanation: The interval [1,3] can be removed and the rest of the intervals are non-overlapping.

• 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.

• 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.

Clarifying Questions

1. Can intervals be unsorted?
   • Yes, the intervals can be given in no particular order.
2. Can intervals consist of negative numbers?
   • Yes, intervals can have negative numbers as long as the input format is valid.
3. What is the range of the interval’s size?
   • Each interval is a pair of integers. There is no explicit constraint provided, assume based on common practice that intervals are reasonable in size.

Strategy

The optimal approach to solve this problem uses a Greedy Algorithm. Here’s the detailed plan:

1. Sort the intervals: First, sort the intervals by their end time. This ensures that we are always considering the interval that closes the earliest next.
2. Iterate through intervals: Keep track of the end point of the last added interval in a non-overlapping sequence.
3. Count removals: Whenever an interval overlaps with the last added interval in our non-overlapping sequence, we increment the removal counter instead of adding the interval and continue.

Implementation

Below is the Python code implementing the above strategy:

def eraseOverlapIntervals(intervals):
    # If there are no intervals, we don't need to remove anything
    if not intervals:
        return 0
    
    # Sort intervals based on end time
    intervals.sort(key=lambda x: x[1])
    
    # Keep count of non-overlapping intervals
    count = 0
    # Initialize the end time of the last included interval to the minimum possible
    prev_end = float('-inf')
    
    for start, end in intervals:
        # If the current interval does not overlap with the last included interval
        if start >= prev_end:
            # Update the end time of the last included interval
            prev_end = end
        else:
            # Otherwise, we increment the count of intervals to be removed
            count += 1
    
    return count

# Example usage
print(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]]))  # Output: 1
print(eraseOverlapIntervals([[1,2],[1,2],[1,2]]))        # Output: 2
print(eraseOverlapIntervals([[1,2],[2,3]]))              # Output: 0

Time Complexity

• Sorting: The time complexity of sorting the intervals is (O(n \log n)), where (n) is the number of intervals.
• Iteration: The complexity of iterating through the intervals is (O(n)).
• Overall: The total time complexity is (O(n \log n)) due to the sorting step being the dominant term.

This approach ensures an efficient solution to identify and remove the minimum number of overlapping intervals.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?