Non Overlapping Intervals - Leetcode Solution

Problem statement: Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example: Input: [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Solution: This problem can be solved using the concept of Greedy Algorithm. The approach is to sort the intervals based on their end time. We need to start with the interval with the smallest end time as it will give us more space to accommodate other intervals. Whenever we find overlapping intervals, we keep the interval with the smallest end time and remove the other one.

1. Sort the intervals based on their end time.
2. Initialize a variable end with the value of negative infinity. This variable will keep track of the end time of the last included interval.
3. Iterate through all intervals.
4. Check if the start time of the current interval is greater than or equal to end. If yes, include the interval and update the value of end with its end time.
5. Else, discard the current interval.
6. Return the number of intervals that were removed (total number of intervals - number of intervals included in step 4).

Code:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        intervals.sort(key=lambda x: x[1])
        end = float('-inf')
        count = 0
        
        for interval in intervals:
            start = interval[0]
            if start >= end:
                end = interval[1]
            else:
                count += 1
                
        return count

Time Complexity: Sorting takes O(nlogn) time and iterating through the intervals takes O(n) time. Thus, the total time complexity is O(nlogn).

Space Complexity: O(1) as we are not using any extra data structure.

1