How do you solve Non-overlapping Intervals?

Sort intervals by their start time. Initialize a variable to track the end of the last included interval. Iterate through intervals starting from the second one. If the current interval's start is at least the previous end, update the previous end to the current interval's end. Otherwise, increment the removal count and update the previous end to the minimum of the current and previous ends. Return the removal count after processing all intervals.

What pattern does Non-overlapping Intervals use?

The Pattern: Greedy Algorithms (Interval Scheduling) The Heuristic: When minimizing removals to avoid overlaps, always keep the interval with the earliest end time among overlapping intervals to maximize the remaining space for future intervals.

Non-overlapping Intervals — Greedy Algorithms

Q: What is the time complexity of Non-overlapping Intervals?

O(n log n). Sorting the intervals takes O(n log n). The subsequent single pass through the intervals is O(n), resulting in overall O(n log n) time.

Problem

Given a collection of intervals, return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

1 ≤ intervals.length ≤ 10⁵
intervals[i].length == 2
−5 * 10⁴ ≤ start_i < end_i ≤ 5 * 10⁴

Example

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

Output: 1

A brute-force approach would check all subsets of intervals to find the largest non-overlapping set, which is exponential in time. Instead, the algorithm sorts intervals by start time and iterates through them, greedily deciding which intervals to keep or remove. For example, after sorting, intervals are [[1,2],[1,3],[2,3],[3,4]]. Starting with the first interval [1,2], the algorithm compares subsequent intervals. When it encounters [1,3], it overlaps with [1,2], so it removes one. It chooses to keep the interval with the earlier end time to maximize room for future intervals. This process continues, resulting in removing only one interval ([1,3]) to achieve a non-overlapping set.

Approach

Straightforward Solution

A brute-force approach tries all subsets of intervals to find the largest non-overlapping subset, which is O(2^n) and infeasible for large inputs.

Core Observation

The fundamental truth is that to minimize removals, one must maximize the number of non-overlapping intervals. Overlaps occur when the start of the current interval is less than the end of the previous chosen interval.

Path to Optimal

Preview

Sorting intervals by start time allows a linear scan to detect overlaps. When an overlap is found, removing the interval with the later end time preserves more space for future intervals, maximizing the count of non-overlapping intervals…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort intervals by their start time. Initialize a variable to track the end of the last included interval…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log n)

Sorting the intervals takes O(n log n). The subsequent single pass through the intervals is O(n), resulting in overall O(n log n) time.

Space

O(1)

The algorithm uses a constant amount of extra space for counters and pointers, not counting the input array.

Solution

Python

1class Solution:
  def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
      intervals.sort()
      res = 0
      prev_end = intervals[0][1]
6
      for start, end in intervals[1:]:
          if start >= prev_end:
              prev_end = end
          else:
              res += 1
              prev_end = min(end, prev_end)
      
      return res

Step-by-Step Solution

1

Sort Intervals by Start Time to Prepare for Greedy Selection

3	`intervals.sort()`

Objective

To order intervals so that overlaps can be detected in a single pass by comparing adjacent intervals.

Key Insight

Sorting intervals by their start time arranges them in a sequence where any overlap must occur between consecutive intervals. This ordering is crucial because it allows the algorithm to detect and resolve overlaps efficiently without backtracking or complex data structures.

Interview Quick-Check

Core Logic

Sorting by start time ensures that any overlapping intervals appear consecutively, enabling a linear scan to detect overlaps.

Complexity

Sorting dominates the time complexity at O(n log n), which is acceptable for large inputs.

2

Iterate Through Intervals to Count and Resolve Overlaps

To scan intervals and increment removal count when overlaps are detected, updating the tracking end time to maintain the earliest possible end.

3

Return the Total Number of Intervals Removed

To output the minimum number of intervals that must be removed to eliminate all overlaps.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 12 Critical

prev_end = min(end, prev_end)

Update prev_end to the minimum of current and previous ends to keep earliest finishing interval.

Updating prev_end to the minimum end time is the core greedy step that guarantees optimality by always keeping the interval that frees up the most room for subsequent intervals.

Line 11 Critical

res += 1

Increment removal count due to overlap.

Incrementing the removal count here is critical because it directly accounts for the minimal number of intervals that must be removed to resolve detected overlaps.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

Why does choosing to keep the interval with the earliest end time among overlapping intervals lead to an optimal solution?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Non-overlapping Intervals from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Non-overlapping Intervals drill

or drill a free problem

1	`class Solution:`
2	`def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:`
3	`intervals.sort()`
4	`res = 0`
5	`prev_end = intervals[0][1]`
6
7	`for start, end in intervals[1:]:`
8	`if start >= prev_end:`
9	`prev_end = end`
10	`else:`
11	`res += 1`
12	`prev_end = min(end, prev_end)`
13
14	`return res`