435. Non-overlapping Intervals - Detailed Explanation

Problem Statement

You’re given an array of intervals intervals where each interval is a pair [start, end). Your goal is to remove the minimum number of intervals so that the remaining intervals are non‑overlapping. Return that minimum number of intervals to remove.

Equivalently, you can ask: what’s the maximum number of non‑overlapping intervals you can keep? Then answer = total_intervals – max_kept.

Examples

Example 1

Input:  intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: Remove [1,3], leaving [[1,2],[2,3],[3,4]] which are non‑overlapping.

Example 2

Input:  intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You must remove two of them, leaving only one interval.

Example 3

Input:  intervals = [[1,2],[2,3]]
Output: 0
Explanation: Already non‑overlapping.

Constraints

• 1 ≤ intervals.length ≤ 10⁵
• intervals[i].length == 2
• −10⁵ ≤ intervals[i][0] < intervals[i][1] ≤ 10⁵

Hints

1. Think about scheduling: if you want to attend as many non‑overlapping meetings as possible, which meeting should you pick first?
2. Sorting by end time and then greedy‑selecting intervals that start after the last chosen end works optimally.
3. Once you know how many you can keep, the number to remove is total minus that.

Greedy‑by‑End‑Time Approach

1. Sort the intervals by their end in ascending order.
2. Initialize:
   • countKept = 0
   • lastEnd = −∞
3. Iterate each interval [s, e] in sorted order:
   • If s ≥ lastEnd, you can keep this interval:
     • countKept++
     • lastEnd = e
   • Otherwise, you must remove it (skip increment).
4. The answer (minimum removals) =

   intervals.length − countKept
   

Why It Works

• By always picking the interval that finishes earliest, you leave as much “room” as possible for subsequent intervals.
• This is the classic interval‑scheduling algorithm proven to be optimal.

Step‑by‑Step Walkthrough (Example 1)

intervals = [[1,2],[2,3],[3,4],[1,3]]
Sorted by end → [[1,2],[2,3],[1,3],[3,4]]

lastEnd = −∞, countKept = 0
  [1,2]: 1 ≥ −∞ → keep → countKept=1, lastEnd=2
  [2,3]: 2 ≥ 2   → keep → countKept=2, lastEnd=3
  [1,3]: 1 < 3   → overlaps → remove
  [3,4]: 3 ≥ 3   → keep → countKept=3, lastEnd=4

Kept = 3 of 4 → removals = 4 − 3 = 1

Complexity Analysis

• Time:
  • Sorting takes O(n log n), where n = number of intervals.
  • One linear scan O(n).
  • Total: O(n log n).
• Space:
  • O(log n) or O(n) depending on sort implementation.
  • O(1) extra for pointers and counters.

Python Code

Java Code

Common Mistakes

• Sorting by start time instead of end time can lead to suboptimal choices.
• Using a less efficient data structure (like checking overlaps via nested loops) yields O(n²) timeouts.
• Off‑by‑one when testing overlap (should allow s == lastEnd as non‑overlapping).

Edge Cases

• All intervals identical → must remove all but one.
• Intervals that just touch ([a,b] and [b,c]) are not overlapping.
• Very large n pushing sort and iteration limits (ensure O(n log n)).

Related Problems

• LeetCode 986. Interval List Intersections (intersecting two sorted interval lists)

• LeetCode 1235. Maximum Profit in Job Scheduling (weighted interval scheduling)