DSA problem
Non-overlapping Intervals
Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove so that the remaining intervals are non-overlapping. Two intervals [a, b] and [c, d] overlap if a < d and c < b; touching at a single endpoint (e.g. [1, 2] and [2, 3]) does NOT count as overlapping.
This is a classical interval scheduling problem: maximize the number of mutually non-overlapping intervals that can be kept, then subtract from n. The greedy algorithm that solves the kept-count is to sort by end time and always pick the interval with the earliest end that does not overlap the previously picked one.
Why earliest end? Among compatible candidates, the one ending earliest leaves the most room for future intervals. Any other choice ends later, so any compatible interval found after a non-greedy choice would also have been compatible with the greedy choice. By induction the greedy schedule is at least as large as any other valid schedule.
The implementation sorts by end ascending, then sweeps. Track prevEnd, initialized to negative infinity (or the end of the first interval after counting it). For each interval, if its start is at least prevEnd, keep it and update prevEnd. Count kept intervals; the answer to the problem is n - kept. Sorting dominates at O(n log n) time with O(1) auxiliary space.
Examples
intervals = [[1,2],[2,3],[3,4],[1,3]]1intervals = [[1,2],[1,2],[1,2]]2intervals = [[1,2],[2,3]]0Constraints
- 1 <= intervals.length <= 10^5
- intervals[i].length == 2
- -5 * 10^4 <= start_i < end_i <= 5 * 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.