Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Non-overlapping Intervals

Greedymedium

Given `intervals` as `[start, end]` pairs, implement `eraseOverlapIntervals(intervals)` returning the minimum number of intervals to remove so the rest do not overlap.

Sample tests

Input: eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]])
Output: 1
Input: eraseOverlapIntervals([[1,2],[1,2],[1,2]])
Output: 2

+ 1 hidden test run on Submit.

Hints

Common pitfalls
  • Sorting by start instead of end keeps the wrong intervals.

Learning resources

  • Wikipedia: Greedy algorithm
Approach & explanation (try first)

Greedily keeping earliest-ending non-overlapping intervals minimizes removals in O(n log n) time.

Loading...
⌘/Ctrl + Enter

Run your code to see results.