Intervals · LC #435
Non-overlapping Intervals
Greedy activity-selection: sort by end time, keep the interval with the earliest end whenever there is a conflict, and count removals.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an array of intervals, find the minimum number of intervals you need to remove to make the rest non-overlapping.
Sample I/O
Input: [[1,2],[2,3],[3,4],[1,3]] Output: 1 (remove [1,3]) Input: [[1,2],[1,2],[1,2]] Output: 2
Intuition
How to Think About It
Intuition
This is the classic Activity Selection Problem. Sorting by end time and always keeping the interval that finishes earliest maximises the number of non-overlapping intervals we can retain - so removals = total − kept.
Core Concept
Sort by end time. Greedily keep an interval if its start >= last kept end (no overlap). Otherwise remove it (increment count). The greedy choice is provably optimal: choosing the earliest-ending interval leaves maximum room for future ones.
When to use
Minimum removal / maximum selection of non-overlapping intervals; scheduling to maximise tasks completed.
When NOT to use
When intervals have weights and you want maximum-weight subset (use DP); when you need the actual removed intervals not just the count.
Key Insights
What to Know Cold
- Sort by END time - not start time - this is the key greedy insight.
- Equivalently: find max non-overlapping intervals kept, answer = n − kept.
- Touching intervals (start == previous end) do NOT overlap; use >= for the keep condition.
- The greedy exchange argument: swapping in an earlier-ending interval never makes things worse.
- O(1) extra space after sort - just track last kept end and a counter.
1 example
Worked Examples
Minimum meeting cancellations
Meetings [[1,2],[2,3],[3,4],[1,3]] - find minimum to cancel.
Sort by end, greedily keep earliest-ending non-overlapping meetings.
Output: 1
Conference-room scheduling, CPU task planning - any resource-constrained selection problem reduces to this.