LeetCode #435: Non-overlapping Intervals

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

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

To solve this problem, we can follow these steps:

1. Sort the intervals by their end time.
2. Initialize a variable end to negative infinity to keep track of the end time of the last interval.
3. Iterate through the intervals and count the number of overlapping intervals. If an interval overlaps with the previous interval, remove it. Otherwise, update the value of end to the end time of the current interval.

Here’s the implementation of the above algorithm:

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

Time Complexity

Sorting the intervals takes O(n log n) time. The iteration through the intervals takes O(n) time. Therefore, the overall time complexity of the algorithm is O(n log n).

Space Complexity

The algorithm uses a constant amount of extra space to store the count and end variables. Therefore, the space complexity of the algorithm is O(1).