Coding interview problems › Intervals

📅 Intervals Medium

Non-overlapping Intervals

Non-overlapping Intervals explained: the greedy earliest-end rule (activity selection) for the fewest removals, a proof idea, tested Python and a live visual.

Also searched as: minimum intervals to remove to avoid overlap · activity selection problem · interval scheduling greedy

📅

Try it live Free

Merge Intervals & Meeting Rooms

On the Merge Intervals timeline, see which intervals pile into the same busy block; each block can keep only intervals that sit end-to-end.

Also useful: Sorting Race: Insertion vs Merge vs Quick

Open the playground →

The problem

Given a list of intervals, return the minimum number of intervals to remove so that the rest do not overlap. Intervals that only touch at an endpoint, like [1, 2] and [2, 3], do not overlap.

Input[[1, 2], [2, 3], [3, 4], [1, 3]]
Output1

Remove [1, 3].

Input[[1, 2], [1, 2], [1, 2]]
Output2

The key insight

Removing the fewest is the same as keeping the most. The classic activity-selection greedy keeps the interval that ends earliest, because it leaves the most room for everything after. Sort by end time, keep each interval that starts at or after the last kept end, and count the rest as removed.

Brute force first: Trying every subset of intervals to keep is exponential; a DP over sorted intervals is O(n²).

Step-by-step approach

  1. Sort the intervals by end time.
  2. Track last_end, the end of the most recently kept interval (start at negative infinity).
  3. For each interval, if its start is >= last_end, keep it and set last_end to its end.
  4. Otherwise it overlaps a kept interval, so count it as removed.
  5. Return the removed count.

Python solution

PYTHON 3tested
def erase_overlap_intervals(intervals):
    removed, last_end = 0, float("-inf")
    for start, end in sorted(intervals, key=lambda iv: iv[1]):
        if start >= last_end:          # fits after the last kept interval
            last_end = end
        else:
            removed += 1               # overlaps: drop it
    return removed

Complexity

TimeO(n log n)
SpaceO(n)

Sorting by end time dominates; the greedy pass is O(n).

Common mistakes

Frequently asked questions

What is the time and space complexity of Non-overlapping Intervals?

O(n log n) time for sorting by end, then O(n) for the pass. Space is O(n) for the sorted copy.

Why does the earliest end time greedy work?

Take any optimal set of kept intervals. Swapping its first interval for the one that ends earliest overall cannot create an overlap, because it ends no later. Repeating the argument shows the greedy keeps as many intervals as the optimum.

How is this related to Minimum Arrows to Burst Balloons?

Both sort by end and greedily sweep. The arrows problem counts the groups that a single point can cover, which is the number of intervals the greedy would keep, with touching counted as overlapping.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Intervals Merge Intervals & Meeting Rooms lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.