72 / 75
Medium
Non-overlapping Intervals
#72arraygreedysortingintervalsdynamic-programming
Sort by end time, greedily keep intervals that end earliest to minimize removals.
Example:
Input:
intervals=[[1,2],[2,3],[3,4],[1,3]]Output:
1 (remove [1,3])Common Mistakes:
- Sorting by start time instead of end time (suboptimal greedy)
- Wrong overlap condition (should be start < end, not <=)
- Trying DP when greedy is sufficient and optimal
- Counting kept intervals instead of removed ones
Notes:
Greedy algorithm: keep intervals that end earliest. Time O(n log n), Space O(1). Similar to activity selection problem.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Sort by end time, greedily keep intervals that end earliest to minimize removals.
Example:
Input:
intervals=[[1,2],[2,3],[3,4],[1,3]]Output:
1 (remove [1,3])Common Mistakes:
- Sorting by start time instead of end time (suboptimal greedy)
- Wrong overlap condition (should be start < end, not <=)
- Trying DP when greedy is sufficient and optimal
- Counting kept intervals instead of removed ones
Notes:
Greedy algorithm: keep intervals that end earliest. Time O(n log n), Space O(1). Similar to activity selection problem.
72/75
Non-overlapping Intervals