Non-overlapping Intervals [Medium] — Greedy Scheduling

Problem Statement#

LeetCode 435 — Non-overlapping Intervals (Medium)

Given an array of intervals where intervals[i] = [starti, endi], return the minimum number of intervals you must remove so that the remaining intervals are non-overlapping.

Two intervals are considered non-overlapping if they share at most one endpoint — e.g., [1, 2] and [2, 3] are non-overlapping because they only touch at 2.

Example 1

Input:  [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: Remove [1,3] and the rest are non-overlapping.

Example 2

Input:  [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] duplicates.

Example 3

Input:  [[1,2],[2,3]]
Output: 0
Explanation: They are already non-overlapping.

Constraints

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

Why This Problem Matters#

This problem is a direct application of the Interval Scheduling Maximization theorem — one of the most celebrated results in combinatorial optimization. Here is the core idea:

If you want to keep as many non-overlapping intervals as possible, you should always pick the interval that ends earliest and never look back.

Because keeping the most intervals is equivalent to removing the fewest, maximizing the number of intervals you keep directly gives you the minimum removals.

You will encounter this pattern in FAANG interviews more often than you might expect. Google uses interval problems in phone screens and on-site rounds because they test whether a candidate can:

1. Spot that a greedy choice exists (not every problem has one).
2. Justify why the greedy choice is safe — proving correctness under pressure.
3. Handle off-by-one details around touching endpoints.

Beyond interviews, the algorithm is the backbone of real systems: CPU task schedulers, meeting-room booking engines, and network packet routing all use variants of this greedy strategy.

The Greedy Insight#

Why sort by end time?#

Intuitively, an interval that ends earlier "gets out of the way" faster. It frees up time on the number line for future intervals to coexist without overlapping. If you instead sort by start time or by length, you can construct counterexamples where a locally good-looking choice blocks several future intervals.

Formal exchange argument (the key interview answer):

Suppose you have an optimal solution that does NOT include the interval with the earliest end time, call it X. Swap whichever interval occupies that slot in the optimal solution for X. Because X ends no later than the swapped-out interval, it cannot create any new conflicts with intervals that come after it. So the modified solution is equally valid — meaning including X is at least as good. By induction, always picking the earliest-ending compatible interval is safe.

The algorithm in plain English#

1. Sort all intervals by their end time (ascending).
2. Initialize prev_end to negative infinity and a removals counter to 0.
3. Walk through each interval in sorted order:
   • If the current interval's start is less than prev_end, the two intervals overlap. Remove the current one (increment removals). We implicitly keep whichever interval already ended at prev_end because it ends earlier.
   • Otherwise, no overlap. Keep the current interval and update prev_end to its end time.
4. Return removals.

One subtlety worth noting: when two intervals overlap, we always discard the later-ending one (the current interval in sorted order), not the earlier one. That is exactly the greedy choice — we keep the one that ends soonest.

Visual Dry Run#

Let us trace through the example [[1,2],[2,3],[3,4],[1,3]] step by step.

Step 0 — Sort by end time:

Original: [[1,2],[2,3],[3,4],[1,3]]
Sorted:   [[1,2],[2,3],[1,3],[3,4]]
          end=2  end=3  end=3  end=4

State: prev_end = -inf, removals = 0

Step 1 — Process [1, 2]

prev_end = -inf
start    = 1
 
1 >= -inf  →  no overlap
→ Keep [1,2], update prev_end = 2
 
State: prev_end=2, removals=0

Timeline so far:

----[1,2]----

Step 2 — Process [2, 3]

prev_end = 2
start    = 2
 
2 >= 2  →  no overlap (touching endpoints are allowed)
→ Keep [2,3], update prev_end = 3
 
State: prev_end=3, removals=0

Timeline so far:

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

Step 3 — Process [1, 3]

prev_end = 3
start    = 1
 
1 < 3  →  OVERLAP
→ Remove [1,3], removals becomes 1
  (We keep the previously accepted [2,3] because it ends at 3, same as [1,3] but was accepted first)
 
State: prev_end=3, removals=1

Timeline — [1,3] is crossed out:

----[1,2][2,3]----  ~~[1,3]~~

Step 4 — Process [3, 4]

prev_end = 3
start    = 3
 
3 >= 3  →  no overlap
→ Keep [3,4], update prev_end = 4
 
State: prev_end=4, removals=1

Final timeline:

----[1,2][2,3][3,4]----

Answer: 1 — matches expected output.

Common Mistakes#

Mistake 1: Sorting by start time instead of end time#

This is the single most common error. Sorting by start time feels natural because we "read" intervals left to right. But it leads to incorrect results. Consider:

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

Sorted by start: [1,10], [2,3], [4,5]. The greedy by-start approach would keep [1,10] first, then be forced to remove both [2,3] and [4,5] (2 removals). The correct answer is 1 (remove [1,10], keep the other two). Always sort by end time.

Mistake 2: Using a strict less-than for the overlap check#

The problem states two intervals are non-overlapping if they share at most one endpoint. So [1,2] and [2,3] are not overlapping. Your overlap condition must be:

current.start < prev_end   # strictly less than → overlap

Not <=. Using <= will incorrectly remove intervals that merely touch, inflating your answer.

Mistake 3: Updating prev_end when you remove an interval#

When an interval overlaps and you decide to remove it, prev_end must not change. You are discarding the current interval and keeping the one that ended at prev_end. If you accidentally update prev_end to the removed interval's end time, your algorithm breaks down because you are tracking an interval that no longer exists in your kept set.

Mistake 4: Forgetting to handle negative coordinates#

The constraints allow start and end values down to -5 * 10^4. Always initialize prev_end to negative infinity (or a sufficiently small integer), not to 0. Initializing to 0 will cause the first interval to be incorrectly removed if it starts before 0.

Mistake 5: Confusing "minimum removals" with "maximum kept"#

The answer is n - max_non_overlapping. Some candidates try to directly compute the maximum number of non-overlapping intervals and forget to subtract from n. While both formulations are correct, mixing them mid-solution causes off-by-one errors. Stick to counting removals directly — it is cleaner.

Solutions#

Python#

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    # Sort intervals by their end time (ascending).
    # This is the core greedy choice: always consider the earliest-ending
    # interval first so we leave maximum room for future intervals.
    intervals.sort(key=lambda x: x[1])
 
    # prev_end tracks the end time of the last interval we decided to KEEP.
    # Initialize to -infinity so the very first interval is never removed.
    prev_end = float('-inf')
 
    # removals counts how many intervals we must delete.
    removals = 0
 
    for start, end in intervals:
        # If the current interval starts before the previous kept interval ends,
        # we have an overlap. We must remove one of them.
        # In sorted order, the current interval ends >= prev_end (since we sorted
        # by end), so removing the current interval is always the greedy choice
        # — it keeps the interval that ends sooner (better for future intervals).
        if start < prev_end:
            removals += 1          # Remove the current interval (implicitly)
            # Do NOT update prev_end — we are keeping the earlier-ending interval.
        else:
            # No overlap: keep the current interval and advance our boundary.
            prev_end = end
 
    return removals

JavaScript#

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    // Sort by end time ascending — the greedy key insight.
    // Earliest-ending intervals are considered first so they leave
    // the maximum amount of "free space" on the timeline.
    intervals.sort((a, b) => a[1] - b[1]);
 
    // prevEnd is the end time of the last interval we chose to KEEP.
    // Use -Infinity so the first interval is always accepted.
    let prevEnd = -Infinity;
 
    // Count of intervals we must remove.
    let removals = 0;
 
    for (const [start, end] of intervals) {
        // Overlap detected: current interval starts before the
        // previously kept interval finishes.
        if (start < prevEnd) {
            // Remove the current interval (it ends later in sorted order,
            // so discarding it is always the better greedy decision).
            removals++;
            // prevEnd stays the same — we are keeping the earlier-ending one.
        } else {
            // No overlap: accept this interval, update the boundary.
            prevEnd = end;
        }
    }
 
    return removals;
};

Complexity Analysis#

The algorithm is essentially optimal: you cannot solve this problem without at least reading all intervals, and any comparison-based sort is bounded below by O(n log n). There is no hash-based trick that avoids the sort here.

Follow-up Questions#

These are questions that FAANG interviewers actually ask after you solve the base problem. Be ready for all of them.

1. What if intervals can have the same end time — how does tie-breaking affect correctness?

Tie-breaking on end time does not matter for correctness. If two intervals have the same end time, picking either one leaves the same boundary for future intervals. Your count of removals will be identical regardless of which tie-breaking rule you use.

2. Can you solve this without sorting? What is the best you can do?

No comparison-based algorithm can beat O(n log n) for the general case (reducible to sorting). If coordinates are bounded integers you could use a counting sort to achieve O(n + C) where C is the coordinate range, but for the given constraints (-5*10^4 to 5*10^4) this is still practical.

3. How does this relate to the "Meeting Rooms II" problem (LeetCode 253)?

Meeting Rooms II asks for the minimum number of rooms needed to hold all meetings simultaneously. That problem uses a min-heap (or two-pointer approach with sorted arrays) to track ongoing meetings. Non-overlapping Intervals asks for minimum removals. Both use sorting as the first step but diverge in what they track afterward. Knowing both demonstrates depth.

4. What if you can remove at most K intervals — what is the maximum number of non-overlapping intervals you can keep?

This becomes a more complex DP/greedy hybrid. For small K you can use DP with dp[i][k] = maximum intervals you can keep ending at interval i with k removals used. For large K the original greedy applies directly.

5. What if the intervals are weighted and you want to maximize the total weight of kept intervals?

This is the Weighted Interval Scheduling problem, which requires dynamic programming (O(n log n) with binary search to find the latest non-overlapping predecessor). The unweighted greedy does NOT generalize to weights.

6. How would you handle this problem in a streaming setting where intervals arrive one at a time?

You cannot sort in a streaming setting. One approach is to maintain a sorted structure (e.g., a balanced BST or sorted list) of kept intervals and use a greedy insertion check. However, the minimum-removals guarantee only holds if you can re-evaluate past decisions, which a pure online algorithm cannot do. In practice, you would process intervals in batches.

This Pattern Solves#

The greedy sort-by-end-time pattern appears across many classic interval problems. Recognizing it instantly is a strong signal to interviewers:

• LeetCode 435 — Non-overlapping Intervals (this problem)
• LeetCode 452 — Minimum Number of Arrows to Burst Balloons (nearly identical greedy, different overlap rule)
• LeetCode 646 — Maximum Length of Pair Chain (same greedy — sort by second element)
• LeetCode 1024 — Video Stitching (greedy interval cover, related idea)
• LeetCode 56 — Merge Intervals (sort by start, merge overlapping ones)
• LeetCode 57 — Insert Interval (insert then merge)
• Activity Selection Problem — classic CS textbook greedy
• CPU Burst Scheduling — OS scheduling algorithms

The mental model: whenever you need to maximize the number of non-conflicting tasks, activities, or intervals, sort by finishing time and greedily pick the earliest-finishing compatible option.

Key Takeaways#

• LeetCode 435 — Non-overlapping Intervals is a Medium asked at Google, Amazon, and Microsoft; sort by end time, then greedily keep the earliest-ending compatible intervals.
• Greedy correctness: keeping the earliest-ending interval maximizes room for future intervals — swapping it for any other choice never improves the result (exchange argument).
• Sort key is the algorithm: sorting by end time (not start time or length) is the single insight that makes the greedy pass work.
• Overlap condition: interval.start < prev_end (strict less-than) because touching endpoints are allowed — using <= overcounts removals.
• Answer is n - count_kept (total intervals minus how many we keep) — equivalently, count how many are removed.
• Time O(n log n) for sort; O(n) for the greedy pass; space O(1) excluding the sort.
• The same greedy pattern (sort by end, keep compatible) powers LC 452 (Minimum Arrows to Burst Balloons) and classic Activity Selection scheduling problems.