DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Non-overlapping Intervals

mediumIntervals

Problem statement

You get a list of intervals [start, end] in no particular order. Return the minimum 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, 4], [2, 3], [3, 6], [5, 7]]

Output: 2

Explanation: At most two can be kept together, for example [2, 3] and [3, 6], so two must go.

Example 2

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

Output: 1

Explanation: Remove [0, 5]; the other three only touch at their endpoints.

Hints

Approach

Greedy by earliest end time.

  1. Sort the intervals by their end.
  2. Keep the first one and remember its end as last_end.
  3. For each next interval:
    • if it starts at or after last_end, keep it and set last_end to its end;
    • otherwise it overlaps something you kept: count it as removed.
  4. Return the removed count.

Why it is safe: among intervals that conflict, the one that ends first leaves the most room for everything after it. Swapping any kept interval for one that ends earlier can never reduce how many more you can fit.

ComplexityTime O(n log n)Space O(1) extra (plus the sort)
Python
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

Follow-up questions

  • Return which intervals to remove, not just how many.
  • There are now k identical rooms instead of one. How many intervals must be rejected?

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.

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?

No, which is why the check is start >= last_end. If the interviewer says touching intervals do conflict, change it to start > last_end.