435. Non Overlapping Intervals

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
Brute Force	Generate all possible combinations of intervals to remove. For each combination, check if remaining intervals are non-overlapping. Return minimum removals needed.	\(O(2^n)\)	\(O(n)\)
Greedy (Implemented)	Sort intervals by start time. Iterate through sorted intervals, when overlap detected, remove the interval with larger end time (keep shorter one). Count total removals.	\(O(n log n)\)	\(O(1)\)

Implementation

PythonJavaScriptGo

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda i: i[0])

        counter = 0

        prev_end = intervals[0][1]
        for curr_start, curr_end in intervals[1:]:
            if curr_start < prev_end:
                counter += 1
                # leave the shorter interval
                prev_end = min(
                    prev_end, curr_end
                )
            else:
                prev_end = curr_end

        return counter