LeetCode 435: Non-overlapping Intervals Solution in Python – A Step-by-Step Guide

What Is LeetCode 435: Non-overlapping Intervals?

In LeetCode 435: Non-overlapping Intervals, you’re given a list of intervals—each a pair of start and end times (e.g., [[1,2], [2,3], [3,4], [1,3]])—and your task is to find the minimum number of intervals to remove so the rest don’t overlap. Two intervals overlap if one’s start time is less than another’s end time (excluding exact endpoints). For example, [[1,2], [1,3]] has an overlap, but [[1,2], [2,3]] doesn’t. It’s like decluttering a timeline, keeping as many events as possible.

Problem Statement

• Input: intervals (List[List[int]])—a list of [start, end] pairs.
• Output: Integer—the minimum number of intervals to remove.
• Rules:
• Intervals [a,b] and [c,d] overlap if a < d and c < b (endpoints touching is okay).
• Remove the fewest intervals to make the rest non-overlapping.

Constraints

• 1 <= intervals.length <= 10^5.
• intervals[i].length == 2.
• -5 * 10^4 <= start_i < end_i <= 5 * 10^4.

Examples to Get Us Started

• Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
• Output: 1 (Remove [1,3]; [1,2], [2,3], [3,4] remain non-overlapping).
• Input: intervals = [[1,2],[1,2],[1,2]]
• Output: 2 (Remove two [1,2]s; one [1,2] stays).
• Input: intervals = [[1,2],[2,3]]
• Output: 0 (No overlaps, nothing to remove).

Understanding the Problem: Clearing the Overlaps

To solve LeetCode 435: Non-overlapping Intervals in Python, we need to minimize removals while maximizing the number of non-overlapping intervals. This screams greedy algorithm—make the best local choice at each step to optimize globally. A brute-force check of all subsets would be O(2^n)—way too slow! Instead, we’ll use:

• Best Solution (Greedy, Sort by End Time): O(n log n) time, O(1) space—optimal and elegant.
• Alternative Solution (Greedy, Sort by Start Time): O(n log n) time, O(1) space—intuitive but less efficient in practice.

Let’s dive into the best solution first—it’s the gold standard for this problem.

Best Solution: Greedy with Sort by End Time

Why This Is the Best Solution

Sorting by end time and greedily picking non-overlapping intervals is the top approach because it maximizes the number of intervals we can keep—O(n log n) time, O(1) space (excluding sorting’s internal space). By prioritizing intervals that end earliest, we leave the most room for others, minimizing removals. It’s like scheduling meetings that finish soonest, freeing up your day for more!

How It Works

Here’s the strategy:

• Step 1: Sort intervals by end time (if equal, start time doesn’t matter much here).
• Step 2: Iterate through sorted intervals:
• Keep the first interval (earliest end).
• For each next interval:
• If its start is ≥ previous end, keep it (no overlap), update previous end.
• If it overlaps (start < previous end), skip it (count removal).
• Step 3: Return the removal count.
• Why It Works:
• Earliest-ending intervals give the most flexibility for what follows.
• Greedy choice ensures maximum non-overlapping set, minimizing removals.

Step-by-Step Example

Example 1: intervals = [[1,2],[2,3],[3,4],[1,3]]

• Sort by End: [[1,2], [2,3], [1,3], [3,4]].
• Process:
• Take [1,2], prev_end = 2, removals = 0.
• [2,3]: start 2 ≥ 2, take it, prev_end = 3, removals = 0.
• [1,3]: start 1 < 3, overlap, removals = 1.
• [3,4]: start 3 ≥ 3, take it, prev_end = 4, removals = 1.
• Result: 1 removal.

Example 2: intervals = [[1,2],[1,2],[1,2]]

• Sort by End: [[1,2], [1,2], [1,2]].
• Process:
• Take [1,2], prev_end = 2, removals = 0.
• [1,2]: start 1 < 2, overlap, removals = 1.
• [1,2]: start 1 < 2, overlap, removals = 2.
• Result: 2 removals.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down for clarity:

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

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

        # Track previous end and count removals
        prev_end = intervals[0][1]
        removals = 0

        # Iterate from second interval
        for i in range(1, len(intervals)):
            start, end = intervals[i]
            # No overlap: keep interval, update prev_end
            if start >= prev_end:
                prev_end = end
            # Overlap: skip this interval, increment removals
            else:
                removals += 1

        return removals

• Line 3-4: Early exit for empty list—0 removals.
• Line 6: Sort by end time (e.g., [[1,2], [1,3]] → [[1,2], [1,3]]).
• Line 9-10: Start with first interval’s end, removals at 0.
• Line 12-17: Loop from second interval:
• Get start, end (e.g., [2,3] → start=2, end=3).
• If start ≥ prev_end, no overlap—keep it, update prev_end.
• If start < prev_end, overlap—skip it, add to removals.
• Line 19: Return total removals.
• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(1)—just a few variables.

It’s like pruning a timeline with surgical precision!

Alternative Solution: Greedy with Sort by Start Time

Why an Alternative Approach?

Sorting by start time and greedily handling overlaps is another angle—still O(n log n) time, O(1) space. It’s less optimal because early-starting intervals might stretch long, forcing more removals, but it’s a natural way to think about scheduling from the beginning. It’s like booking meetings as they come up, canceling later ones that clash.

How It Works

• Step 1: Sort by start time (then end time if tied).
• Step 2: Iterate:
• Keep first interval.
• Compare with next: remove the one with later end time if they overlap.
• Step 3: Count removals.

Step-by-Step Example

Example: intervals = [[1,2],[2,3],[3,4],[1,3]]

• Sort by Start: [[1,2], [1,3], [2,3], [3,4]].
• Process:
• Take [1,2], prev = [1,2], removals = 0.
• [1,3]: overlaps (1 < 2), remove [1,3] (end 3 > 2), removals = 1.
• [2,3]: no overlap (2 ≥ 2), prev = [2,3].
• [3,4]: no overlap (3 ≥ 3), prev = [3,4].
• Result: 1 removal.

Code for Start-Time Approach

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

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

        prev = intervals[0]
        removals = 0

        for i in range(1, len(intervals)):
            curr = intervals[i]
            # Overlap: remove interval with later end
            if curr[0] < prev[1]:
                if curr[1] < prev[1]:
                    prev = curr  # Keep shorter one
                removals += 1
            else:
                prev = curr  # No overlap, move forward

        return removals

• Time Complexity: O(n log n)—sorting.
• Space Complexity: O(1)—minimal extra space.

It works, but end-time sorting is slicker.

Comparing the Two Solutions

• Sort by End Time (Best):
• Pros: O(n log n), O(1), maximizes kept intervals, fewer removals.
• Cons: Less intuitive at first.
• Sort by Start Time (Alternative):
• Pros: O(n log n), O(1), follows natural order.
• Cons: May remove more than necessary.

End-time wins for optimality.

Edge Cases and More Examples

• Input: [] → 0.
• Input: [[1,2]] → 0.
• Input: [[1,3],[2,4],[3,5]] → 1 (end-time: remove [2,4]).

Both handle these smoothly.

Complexity Recap

• End-Time: Time O(n log n), Space O(1).
• Start-Time: Time O(n log n), Space O(1).

End-time’s greedier greed wins.

Key Takeaways

• End-Time Greedy: Less is more—fewer removals.
• Start-Time Greedy: Intuitive but less efficient.
• Python Tip: Sorting is your friend—see [Python Basics](/python/basics).

Final Thoughts: Clear That Schedule

LeetCode 435: Non-overlapping Intervals in Python is a greedy algorithm gem. Sorting by end time is your fast track to success, while start-time sorting offers a scenic route. Want more greedy fun? Try LeetCode 452: Minimum Number of Arrows to Burst Balloons or LeetCode 646: Maximum Length of Pair Chain. Ready to declutter some intervals? Head to Solve LeetCode 435 on LeetCode and optimize that timeline today—your coding journey just got smoother!