The Greedy Trick That Solves Non-overlapping Intervals [Leetcode : 435]

EverythingGuy

3 min read

·

Aug 3, 2026

--

Listen

Share

At first glance, this problem feels simple:

If two intervals overlap, remove one.

But the real challenge is:

Which interval should we remove?

Once we answer that question, the greedy solution becomes obvious.

First Thought

My initial idea was:

1. Sort the intervals.
2. Whenever I find an overlap:

• removals += 1

For example,

[1,2]
[2,3]
[1,3]

Since [1,3] overlaps with the others, remove it.

This seems reasonable…

Until we see this example.

The Greedy Insight

Consider:

[1,100]
[2,3]
[3,4]

Suppose we remove:

[2,3]

We are left with:

[1,100]
[3,4]

Now [3,4] also overlaps with [1,100].

Total removals:

2

Instead, remove:

[1,100]

Now we keep:

[2,3]
[3,4]

Only:

1

removal is needed.

This immediately gives us the greedy observation:

Whenever two intervals overlap, keep the interval that ends earlier.

Why?

Because an interval that finishes earlier leaves more room for future intervals.

Why Sort By End Time?

At first, I wondered whether sorting by start time would work.

Consider:

[1,100]
[2,3]

If sorted by start time:

[1,100]
[2,3]

An overlap occurs.

Now I have to decide:

Should I remove [1,100]?
Or should I remove [2,3]?

So sorting by start time still requires another greedy decision.

Instead, sort by end time.

[2,3]
[1,100]

Now the interval we’ve already kept always has the earliest ending time.

If another interval overlaps with it, we already know which one to remove.

No extra comparison.

No extra decision.

Walking Through the Algorithm

After sorting by end time:

[2,3]
[3,4]
[1,100]

We always keep the first interval.

previousEnd = 3

Now process the next interval.

Current:

[3,4]

Check:

previousEnd <= start

3 <= 3

No overlap.

Keep it.

Update:

previousEnd = 4

Next interval:

[1,100]

Check:

1 < 4

Overlap.

Simply remove it.

removals += 1

Notice that we do not update previousEnd.

Why Don’t We Update previousEnd?

This is the most important greedy idea.

Suppose we have:

[2,3]
[1,100]
[4,5]

Current state:

previousEnd = 3

The current interval is:

[1,100]

If we update:

previousEnd = 100

Then the next interval:

[4,5]

would incorrectly appear to overlap.

Instead, we keep:

previousEnd = 3

because an earlier ending interval always leaves more room for future intervals.

That is exactly why we discard the current interval instead.

Variables Needed

Only two variables are required.

previousEnd

Stores the end of the last interval we decided to keep.

removals

Counts how many intervals we remove.

Complete Algorithm

Sort intervals by end time
        ↓
Keep the first interval
        ↓
previousEnd = first interval's end
        ↓

For every remaining interval    Is previousEnd <= start ?        Yes            Keep current interval            previousEnd = current end        No            Remove current interval            removals += 1

Why This Greedy Strategy Works

Sorting by end time guarantees that the interval we’ve already kept always has the smallest ending time among all valid choices.

So whenever an overlap occurs:

Keep the interval that ends earlier.

Remove the interval that ends later.

An earlier ending interval always leaves the maximum room for future intervals, allowing us to keep as many intervals as possible while minimizing removals.

Complexity

Time Complexity

O(n log n)

Sorting dominates the runtime.

Space Complexity

O(1)

Only two extra variables are used.

Code

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

        # Sort intervals by ending time.
        intervals.sort(key=lambda interval: interval[1])        # Keep the first interval.
        previousEnd = intervals[0][1]
        removals = 0        # Process the remaining intervals.
        for start, end in intervals[1:]:            # No overlap: keep the interval.
            if previousEnd <= start:
                previousEnd = end            # Overlap: remove the current interval.
            else:
                removals += 1        return removals

Interview Takeaway

The key observation is simple:

Whenever two intervals overlap, always keep the interval with the smaller end time.

Sorting by end time ensures that this decision has already been made for us.

So during traversal:

• If there is no overlap:
• Keep the interval.
• Update previousEnd.
• If there is an overlap:
• Remove the current interval.
• Keep previousEnd unchanged.

This greedy strategy is optimal because keeping the earliest ending interval always leaves the maximum room for all future intervals.