mafeshsho8lmafeshsho8l
Get Started
All coding questions

Non-overlapping Intervals

medium
NeetCode 150intervalsgreedysorting

Problem

Given a list of intervals, return the minimum number you must remove so that the remaining intervals do not overlap.

Examples

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Removing [1, 3] leaves the rest disjoint.
Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2
Two duplicates must go.

Constraints

  • • 1 <= intervals.length <= 10^5
  • • Each interval start is less than its end
Hints(tap to reveal)
  • 1. Greedily keep intervals that end earliest.
  • 2. Sort by end time and count conflicts.
Optimal approach(spoiler)
  1. Sort the intervals by their end value.
  2. Track the end of the last kept interval.
  3. If the next interval starts before that end, it overlaps and must be removed.
  4. Otherwise keep it and update the tracked end.
  5. O(n log n) time, O(1) extra space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor