Understanding Non-overlapping Intervals
Return the fewest intervals to remove so the remaining intervals do not overlap. Touching endpoints are allowed.
How it works
Keeping the compatible interval that ends earliest leaves the most room for future choices.
Sort intervals by end time. Keep the next interval when its start is at least the last kept end. Subtract the number kept from the total.
Try an example
Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Keeping the compatible interval that ends earliest leaves the most room for future choices.
Constraints
- 0–32 intervals [start, end], with start < end and integer endpoints between -1,000,000 and 1,000,000.
- Duplicate intervals are allowed and overlap one another.
Use the simulator
Change the input, then choose Visualize input. Use Next and Previous to inspect each decision, or Play to advance automatically. Compare approaches and their complexity. Choose Try yourself to write JavaScript, select My code and Visualize code to inspect its execution, or Run Tests to check results.
Execution happens in your browser. Drafts are saved locally; avoid entering secrets or sensitive information.