Non-Overlapping Intervals — LeetCode 435 Greedy Sort by End

Problem Statement#

Given an array of intervals, return the minimum number you must remove so the rest are non-overlapping. Two intervals that only touch at an endpoint do not overlap.

Constraints:

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

Input:  intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1

Input:  intervals = [[1,2],[1,2],[1,2]]
Output: 2

Why This Problem Matters#

Non-Overlapping Intervals is the textbook greedy interview problem at Meta, Amazon, and Google. It is a direct rephrasing of the classical activity selection problem from algorithm theory, which means recruiters frequently ask "have you proved correctness" and follow up with "what changes if we sort by start instead."

The exchange argument used here is the same one used in Minimum Number of Arrows to Burst Balloons, Course Schedule III, and Maximum Number of Events. Mastering it once unlocks a whole subtree of FAANG interval problems.

This problem is on Meta's tagged list and Amazon's high-frequency list. Bloomberg loves the variant where ties are broken by start time. Failing to sort by end is the most common interview-killer mistake on this question.

The Core Insight#

Greedy choice: among all remaining intervals, keep the one with the smallest end time. This leaves the maximum room for future intervals. Sort by end ascending, then sweep: if the current interval starts at or after the last kept end, keep it; otherwise, drop it.

Exchange argument: suppose an optimal solution chose an interval ending later than the greedy choice at some step. Swap it with the greedy interval (smaller end). The new solution still non-overlaps because a smaller end can only help, never hurt, future picks.

Visual Dry Run#

Total intervals = 4, kept = 3, remove = 1.

Solution (Optimal)#

class Solution:
    def eraseOverlapIntervals(self, intervals):
        intervals.sort(key=lambda x: x[1])
        prev_end = float('-inf')
        kept = 0
        for start, end in intervals:
            if start >= prev_end:
                kept += 1
                prev_end = end
        return len(intervals) - kept

var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a, b) => a[1] - b[1]);
    let prevEnd = -Infinity, kept = 0;
    for (const [start, end] of intervals) {
        if (start >= prevEnd) {
            kept++;
            prevEnd = end;
        }
    }
    return intervals.length - kept;
};

Time: O(n log n) — sorting dominates the linear sweep Space: O(1) extra besides the in-place sort

Common Mistakes#

• Sorting by start time — fails on cases like [[1,100],[2,3],[3,4]] where you keep the wide interval
• Counting removed instead of kept and then forgetting to subtract from total
• Using > instead of >= for the start comparison — touching endpoints do not overlap
• Trying DP first — DP works but is O(n log n) anyway and the greedy is cleaner
• Returning kept instead of len(intervals) - kept

Interview Tips#

• Always sort by end first; explicitly state why start sort is wrong
• Mention the connection to activity selection from CLRS
• Note that this is the foundation for Minimum Arrows to Burst Balloons (just change >= to >)

Follow-up Questions#

• What if intervals are weighted and you maximize weight kept? Hint: weighted interval scheduling DP
• What if you must remove the minimum end-points instead of intervals? Hint: same algorithm, different return
• Stream the intervals — can you do it online? Hint: maintain a heap by end
• What about non-overlapping intervals on a circular timeline? Hint: try every starting interval
• How would you parallelize across many machines? Hint: divide-and-conquer with sweep merge

Key Takeaways#

• LeetCode 435 Non-Overlapping Intervals is solved by sort-by-end greedy in O(n log n)
• The greedy choice is the earliest-ending compatible interval
• Exchange argument proves no other ordering yields a higher kept count
• Use start >= prev_end since endpoint-only contact is allowed
• Same template solves Min Arrows, Activity Selection, and Maximum Events
• Sorting by start is a classic bug — verify on the [[1,100],[2,3]] test case
• Final answer is len(intervals) - kept, not kept itself