LeetCode 435: Non Overlapping Intervals — Step-by-Step Visual Trace

Medium — Greedy | Sorting | Intervals | Array

The Problem

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

Approach

Sort intervals by their end times, then greedily select non-overlapping intervals by keeping those that end earliest. The greedy approach works because choosing intervals with earlier end times leaves more room for future intervals.

Time: O(n log n) · Space: O(1)

Code

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        intervals.sort(key=lambda x: x[1])
        non_overlapping = 1  # Count of non-overlapping intervals
        prev_end = intervals[0][1]

        for i in range(1, len(intervals)):
            if intervals[i][0] >= prev_end:
                non_overlapping += 1
                prev_end = intervals[i][1]

        return len(intervals) - non_overlapping

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments