#132 Medium Time O(n log n) Space O(1) Animated

Non-overlapping Intervals

Find minimum intervals to remove so rest are non-overlapping.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Sort intervals, then maintain one boundary

After sorting, overlap decisions depend only on the active interval and the next start.

Approach: Greedy (Sort by End Time)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

After sorting, overlap decisions depend only on the active interval and the next start.

Common Pitfall

Compare the next start against the current end, not against the original unsorted input.

Description

Find minimum intervals to remove so rest are non-overlapping.

Constraints

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

Solution — Greedy (Sort by End Time)

TimeO(n log n) SpaceO(1)

Implementation Plan

Translate the invariant into these small, testable moves.

Sort by the relevant endpoint.
Initialize the active interval.
Merge or select based on overlap.
Update the active boundary.

def eraseOverlapIntervals(intervals):
    intervals.sort()
    res = 0
    prevEnd = intervals[0][1]
    
    for start, end in intervals[1:]:
        if start >= prevEnd:
            prevEnd = end
        else:
            res += 1
            prevEnd = min(end, prevEnd)
            
    return res

Merge Intervals

Meeting Rooms

Non-overlapping Intervals

Steps

Description

Constraints

Tags

Solution — Greedy (Sort by End Time)