Skip to main content
DSA patterns

Non-overlapping Intervals

mediumIntervals

Problem statement

You get a list of intervals [start, end] in no particular order. Return the smallest number of intervals to remove so that the ones left do not overlap each other.

Intervals that only touch at an endpoint, such as [1, 3] and [3, 5], do not overlap.

Examples

Example 1

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

Output: 1

Explanation: Remove [1, 3]. The other three only touch at their endpoints, so they do not overlap.

Example 2

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

Output: 2

Explanation: All three are identical and overlap each other. Keep one and remove the other two.

Hints

Hint 1: Removing the fewest intervals is the same as keeping the most. Think about which intervals to keep instead.

Approach

Optimal: Greedy by earliest end

Intuition

Among intervals that compete for the same time, the one that ends first leaves the most room for everything after it. So sort by end time and keep an interval whenever it fits after the last kept one. Swapping any kept interval for one that ends earlier can never reduce how many more you can fit, which is why this greedy choice is safe. It beats the DP because one sorted pass replaces the n² comparisons.

Steps

  1. Sort the intervals by their end.
  2. Set last_end to minus infinity and removed = 0.
  3. For each interval: if start >= last_end, keep it and set last_end = end.
  4. Otherwise it overlaps the last kept interval, so add 1 to removed.
  5. Return removed.

Dry run

intervals = [[1, 2], [2, 3], [3, 4], [1, 3]], sorted by end: [1, 2], [2, 3], [1, 3], [3, 4]

interval start >= last_end? action last_end removed
[1, 2] yes (-inf) keep 2 0
[2, 3] yes (2 >= 2) keep 3 0
[1, 3] no (1 < 3) remove 3 1
[3, 4] yes (3 >= 3) keep 4 1

The answer is 1.

Edge cases: an empty list returns 0. Identical intervals keep the first and remove the rest.

Complexity

Time O(n log n) - Sorting by end time costs O(n log n). The scan after it visits each interval once, which is O(n). Sorting is the slowest part.

Space O(1) - Besides the sort, we keep only `last_end` and the `removed` counter. The sort itself may use O(n) space depending on the language. No table or recursion is needed.

class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        removed = 0
        last_end = float("-inf")
        for start, end in sorted(intervals, key=lambda iv: iv[1]):
            if start >= last_end:
                last_end = end      # keep it
            else:
                removed += 1        # overlaps the last kept interval
        return removed


if __name__ == "__main__":
    print(Solution().eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]]))
    print(Solution().eraseOverlapIntervals([[1, 2], [1, 2], [1, 2]]))
RecapThe whole problem in a few lines, for the night before
  • Spot it: remove the fewest intervals so none overlap
  • Idea: greedy: sort by end time, keep an interval if it starts at or after the last kept end, otherwise count a removal
  • Cost: O(n log n) time, O(1) extra space
  • Trap: sort by end, not start; and intervals that only touch (end == start) do not overlap

Interview follow-ups

  • Return which intervals to remove, not just how many.

    Keep the same greedy sort by end time, but carry the original interval (or its index) along with each sorted entry. When an interval overlaps the last kept one, add it to a removed list instead of only increasing a counter. Return that list at the end. Time stays O(n log n) and space grows to O(n) for the list. Several answers can be valid, and any list of the minimum size is correct.

  • There are now k identical rooms instead of one. How many intervals must be rejected?

    Sort the intervals by start time and keep the end times of the intervals currently placed in rooms. For each new interval, first drop every active interval that has already ended. Then add the new one. If more than k intervals are now active, reject the one with the latest end time, because it blocks the most future intervals. Count each rejection. Keeping the active end times in a sorted structure gives O(n log n) time. With k = 1 this is the original problem.

Frequently asked questions

Sorting by start and keeping the earliest-starting interval fails on [[0, 10], [1, 2], [3, 4]]: you would keep [0, 10] and have to drop the other two. Sorting by end keeps [1, 2] and [3, 4] and drops only one. A long interval that starts early blocks a lot of time, and sorting by end avoids picking it first.

It is the scheduling question behind booking a single shared resource: given requested windows for one staging environment, one maintenance slot or one on-call engineer, what is the fewest requests you have to reject so the rest do not clash? The same pattern also appears in meeting-room and change-window planning.

No, which is why the check is start >= last_end. If the interviewer says touching intervals do conflict, change it to start > last_end. Always ask this question out loud, because it changes the answer on inputs like Example 1.

They are related but not the same. Merge Intervals combines overlapping intervals into bigger ones and keeps all the time covered. This problem keeps some intervals and throws the others away, so it is a choice problem and needs a greedy rule.