Data Structures19 sections · 729 units
Open in Course

Problem - Non-overlapping Intervals

Minimum removals

Given intervals, find the minimum number of intervals to remove so the rest are non-overlapping. Example: [[1,2],[2,3],[3,4],[1,3]][[1,2], [2,3], [3,4], [1,3]] needs 1 removal.

Remove [1,3][1,3] and the rest don't overlap. You're solving the complement of interval scheduling: minimize removals = maximize kept intervals. Constraints: up to 10510^5 intervals.