Non-overlapping Intervals Python Solution

lcpy gen -n 435   # by problem number
lcpy gen -s non_overlapping_intervals   # by problem name

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.

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.

class Solution:
    # Time: O(n log n) - sorting dominates
    # Space: O(1) - no extra space used
    def erase_overlap_intervals(self, intervals: list[list[int]]) -> int:
        """
        Find minimum number of intervals to remove to make non-overlapping.
        Uses greedy approach: sort by end time and keep intervals with earliest end times.
        """
        if not intervals:
            return 0

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

        count = 0
        prev_end = intervals[0][1]

        for i in range(1, len(intervals)):
            # If current interval starts before previous ends, it overlaps
            if intervals[i][0] < prev_end:
                count += 1  # Remove this interval
            else:
                # No overlap, update previous end time
                prev_end = intervals[i][1]

        return count