Non-overlapping Intervals

Problem Statement

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note: You may assume the interval's end point is always bigger than its start point. Intervals [1,2] and [2,3] have borders "touching" but they don't overlap each other.

Examples

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints

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

Solution Approach

This is a classic greedy algorithm problem, also known as the Activity Selection Problem or Interval Scheduling Maximization.

Key Insight

Sort by end time and greedily keep intervals that end earliest!

The intuition is: if we keep intervals that end early, we leave more room for future intervals. This minimizes the number of intervals we need to remove.

Why Sort by End Time?

Consider intervals [[1,100], [11,22], [1,11], [2,12]]:

• If we sort by start time: We might keep [1,100] which blocks many other intervals
• If we sort by end time: We keep [1,11], then [11,22], maximizing the count!

Sorting by end time ensures we make locally optimal choices that lead to a globally optimal solution.

Algorithm Steps

1. Sort intervals by end time (ascending)
2. Initialize:
   • prevEnd = first interval's end time
   • removed = 0 (count of removed intervals)
3. For each subsequent interval [start, end]:
   • If start >= prevEnd: No overlap, keep it! Update prevEnd = end
   • If start < prevEnd: Overlap detected, remove this interval, increment removed
4. Return removed

Why This Works (Greedy Choice Property)

At each step, we make a greedy choice: "Keep the interval with the earliest end time among all valid options."

This is optimal because:

• An interval ending early leaves more space for future intervals
• If we replaced our choice with a later-ending interval, we'd have less room
• This never increases the number of removals needed

Example Walkthrough

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

1. Sort by end time: [[1,2], [1,3], [2,3], [3,4]]
2. Keep [1,2], set prevEnd = 2, removed = 0
3. Check [1,3]: 1 < 2 → Overlap! Remove it, removed = 1
4. Check [2,3]: 2 >= 2 → No overlap, keep it, prevEnd = 3
5. Check [3,4]: 3 >= 3 → No overlap, keep it, prevEnd = 4
6. Result: removed = 1

Time & Space Complexity

• Time Complexity: O(n log n)

  • Sorting: O(n log n)
  • Single pass: O(n)
  • Total: O(n log n)

• Space Complexity: O(1) or O(log n)

  • O(1) if we sort in-place
  • O(log n) for recursion stack in sorting algorithm

Java Solution

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;

        // Sort by end time (greedy choice)
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int prevEnd = intervals[0][1];
        int removed = 0;

        // Check each interval for overlap
        for (int i = 1; i < intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];

            if (start < prevEnd) {
                // Overlap detected - remove this interval
                removed++;
            } else {
                // No overlap - keep this interval
                prevEnd = end;
            }
        }

        return removed;
    }
}

Python Solution

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    if not intervals:
        return 0

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

    prev_end = intervals[0][1]
    removed = 0

    # Check each interval for overlap
    for i in range(1, len(intervals)):
        start, end = intervals[i]

        if start < prev_end:
            # Overlap detected - remove this interval
            removed += 1
        else:
            # No overlap - keep this interval
            prev_end = end

    return removed

Alternative Approach: Sort by Start Time

You can also sort by start time, but the logic is more complex:

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    int prevEnd = intervals[0][1];
    int removed = 0;

    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < prevEnd) {
            // Overlap - remove the one with later end time
            removed++;
            prevEnd = Math.min(prevEnd, intervals[i][1]);
        } else {
            prevEnd = intervals[i][1];
        }
    }

    return removed;
}

Note: Sorting by end time is simpler and more intuitive!

Related Problems

• Meeting Rooms II (LeetCode 253): Find minimum meeting rooms needed
• Merge Intervals (LeetCode 56): Merge overlapping intervals
• Insert Interval (LeetCode 57): Insert and merge a new interval
• Maximum Length of Pair Chain (LeetCode 646): Similar greedy approach

Pattern Recognition

This problem demonstrates:

• Greedy Algorithm pattern
• Activity Selection problem
• Interval Scheduling optimization
• Sort + Scan technique
• Inverse of "Maximum Non-overlapping Intervals" problem

Common Mistakes to Avoid

1. ❌ Sorting by start time without proper overlap handling
2. ❌ Trying Dynamic Programming (overkill for this problem)
3. ❌ Not understanding why greedy works here
4. ❌ Confusing "remove minimum" with "keep maximum"

Tips for Interviews

• Explain WHY sorting by end time works (greedy proof)
• Mention the time complexity upfront
• Consider edge cases: empty array, no overlaps, all overlaps
• Relate to Activity Selection Problem if you know it
• Draw a timeline to visualize the approach