Approach Summary
Sort by end time. Greedily keep intervals with the earliest end. Count how many must be removed (total - kept).
Practice Mode
3 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Greedy Interval Scheduling (Optimal) | O(n log n) | O(1) | Sort by start time, and on overlap greedily retain the interval with the earlier end time. |
| 2 Approach 2: Dynamic Programming Longest Non-Overlapping Subsequence (Baseline) | O(n²) | O(n) | Sorts intervals by start time and uses O(n²) DP to find the maximum chain of compatible intervals. |
| 3 Approach 2: Dynamic Programming Longest Non-Overlapping Subsequence (Baseline) | O(n²) | O(n) | Sorts intervals by start time and uses O(n²) DP to find the maximum chain of compatible intervals. |
Step 1: Baseline
Approach 1: Greedy Interval Scheduling (Optimal)
Time: O(n log n)
Space: O(1)
Whenever two intervals overlap, keeping the interval that finishes earlier always leaves more room for subsequent intervals. Hence, we greedily keep min(end, intervals[i][1]) and increment removal count.
Approach 1: Greedy Interval Scheduling (Optimal) Implementation
Approach 1: Greedy Interval Scheduling (Optimal)
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
int end = intervals[0][1], count = 0;
for (int i = 1; i < intervals.length; i++) {
if (end > intervals[i][0]) {
count++;
end = Math.min(end, intervals[i][1]);
} else {
end = intervals[i][1];
}
}
return count;
}
}class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
int end = intervals[0][1], count = 0;
for (int i = 1; i < intervals.size(); i++) {
if (end > intervals[i][0]) {
count++;
end = min(end, intervals[i][1]);
} else {
end = intervals[i][1];
}
}
return count;
}
};class Solution:
def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
intervals.sort(key=lambda x: x[0])
count = 0
end = intervals[0][1]
for i in range(1, len(intervals)):
if end > intervals[i][0]:
count += 1
end = min(end, intervals[i][1])
else:
end = intervals[i][1]
return countfunction eraseOverlapIntervals(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
let end = intervals[0][1], count = 0;
for (let i = 1; i < intervals.length; i++) {
if (end > intervals[i][0]) {
count++;
end = Math.min(end, intervals[i][1]);
} else {
end = intervals[i][1];
}
}
return count;
} Step 2
Approach 2: Dynamic Programming Longest Non-Overlapping Subsequence (Baseline)
Time: O(n²)
Space: O(n)
Sorts intervals by start time. Let dp[i] be the maximum number of non-overlapping intervals ending at index i. For each j < i, if intervals[j][1] <= intervals[i][0], dp[i] = max(dp[i], dp[j] + 1). Total intervals to remove is n - max(dp).
Approach 2: Dynamic Programming Longest Non-Overlapping Subsequence (Baseline) Implementation
Approach 2: Dynamic Programming Longest Non-Overlapping Subsequence (Baseline)
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
int n = intervals.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxChain = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxChain = Math.max(maxChain, dp[i]);
}
return n - maxChain;
}
}class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end());
int n = intervals.size();
vector<int> dp(n, 1);
int maxChain = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxChain = max(maxChain, dp[i]);
}
return n - maxChain;
}
};class Solution:
def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
if not intervals: return 0
intervals.sort(key=lambda x: x[0])
n = len(intervals)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if intervals[j][1] <= intervals[i][0]:
dp[i] = max(dp[i], dp[j] + 1)
return n - max(dp)function eraseOverlapIntervals(intervals) {
if (!intervals.length) return 0;
intervals.sort((a, b) => a[0] - b[0]);
const n = intervals.length;
const dp = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return n - Math.max(...dp);
} Step 2: Most Optimized
Approach 2: Dynamic Programming Longest Non-Overlapping Subsequence (Baseline)
Time: O(n²)
Space: O(n)
Sorts intervals by start time. Let dp[i] be the maximum number of non-overlapping intervals ending at index i. For each j < i, if intervals[j][1] <= intervals[i][0], dp[i] = max(dp[i], dp[j] + 1). Total intervals to remove is n - max(dp).
Approach 2: Dynamic Programming Longest Non-Overlapping Subsequence (Baseline) Implementation
Approach 2: Dynamic Programming Longest Non-Overlapping Subsequence (Baseline)
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
int n = intervals.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxChain = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxChain = Math.max(maxChain, dp[i]);
}
return n - maxChain;
}
}class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end());
int n = intervals.size();
vector<int> dp(n, 1);
int maxChain = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxChain = max(maxChain, dp[i]);
}
return n - maxChain;
}
};class Solution:
def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
if not intervals: return 0
intervals.sort(key=lambda x: x[0])
n = len(intervals)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if intervals[j][1] <= intervals[i][0]:
dp[i] = max(dp[i], dp[j] + 1)
return n - max(dp)function eraseOverlapIntervals(intervals) {
if (!intervals.length) return 0;
intervals.sort((a, b) => a[0] - b[0]);
const n = intervals.length;
const dp = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return n - Math.max(...dp);
}Edge Cases to Watch
- No overlapping intervals (returns 0)
- All intervals identical (returns n - 1)
- Intervals touching at endpoint (e.g. [1, 2] and [2, 3] do not overlap; returns 0)
Algorithmic Pattern
View Pattern Guide →
Master the Greedy Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Greedy pattern.
How to Recognize This Pattern
- "Minimum intervals to remove so none overlap"
- Greedy: always keep interval with earliest end time
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(1)
Tags
Array Greedy Dynamic Programming Sorting
Frequently Asked Questions
What is the optimal time and space complexity for Non-overlapping Intervals?
The optimal solution for Non-overlapping Intervals achieves O(n log n) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n log n) due to sorting. The subsequent pass takes O(n) time. Space complexity is O(1) auxiliary space beyond the sorting buffer.
How do I identify that Non-overlapping Intervals requires the Greedy pattern?
In technical interviews, look for key problem signals: "Minimum intervals to remove so none overlap"; Greedy: always keep interval with earliest end time. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Greedy strategy.
What critical edge cases must be handled in Non-overlapping Intervals?
Essential edge cases to verify include: No overlapping intervals (returns 0); All intervals identical (returns n - 1); Intervals touching at endpoint (e.g. [1, 2] and [2, 3] do not overlap; returns 0). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Non-overlapping Intervals?
Non-overlapping Intervals is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Google, Facebook.