Log inSign up
mediumLeetCodeNot Started

Non-overlapping Intervals

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

Given an array of intervals intervals where intervals[i] = [start_i, end_i].

Return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which touch at a single point (e.g. [1, 2] and [2, 3]) are non-overlapping.

Example 1 · Example 1: Single Overlap Removal:

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

Example 2 · Example 2: All Overlapping:

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2
Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

Constraints:

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • -5 * 104 <= start_i < end_i <= 5 * 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the duality between interval maximization and removal minimization.
  • Prove why dropping the interval that extends furthest right minimizes future collisions.
  • Implement the greedy solution across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Interval overlap removal minimization.
  • Requires remaining intervals to be mutually disjoint.
  • Touching endpoints [1, 2] and [2, 3] are valid.

Algorithmic Decision Tree:

  • Sort by end ascending.
  • If curr.start < lastEnd: removals++.
  • Else: lastEnd = curr.end.

Connected Patterns:

Activity SelectionMinimum Number of Arrows to Burst BalloonsMerge Intervals

1. Recursive Maximum Compatible Subset Search

Intuition

Sort intervals by start coordinate and recursively determine whether to include or exclude each interval. Return n minus the max compatible subset size.

Algorithm

  1. Step 1: Sort intervals by start time.
  2. Step 2: Define recursive solve(idx, lastEnd) returning max non-overlapping count.
  3. Step 3: If idx == n, return 0.
  4. Step 4: notTake = solve(idx + 1, lastEnd).
  5. Step 5: If intervals[idx][0] >= lastEnd: take = 1 + solve(idx + 1, intervals[idx][1]).
  6. Step 6: Return intervals.length - max(take, notTake).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int idx, int lastEnd, const vector<vector<int>>& intervals) {
9 if (idx == intervals.size()) return 0;
10 int notTake = solve(idx + 1, lastEnd, intervals);
11 int take = 0;
12 if (intervals[idx][0] >= lastEnd) {
13 take = 1 + solve(idx + 1, intervals[idx][1], intervals);
14 }
15 return max(take, notTake);
16 }
17public:
18 int eraseOverlapIntervals(vector<vector<int>>& intervals) {
19 sort(intervals.begin(), intervals.end());
20 int maxKept = solve(0, -1e9, intervals);
21 return intervals.size() - maxKept;
22 }
23};
24
25int main() {
26 Solution sol;
27 vector<vector<int>> intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
28 cout << "Min Removals: " << sol.eraseOverlapIntervals(intervals) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(2^N)
  • Space complexity: O(N)

2. Longest Non-Overlapping Subsequence DP

Intuition

Sort intervals by start time. Use an O(N2) dynamic programming array where dp[i] is the maximum non-overlapping intervals ending at index i.

Algorithm

  1. Step 1: Sort intervals by start time.
  2. Step 2: Initialize dp array of size n with all 1s.
  3. Step 3: For i from 1 to n - 1 and j from 0 to i - 1:
  4. Step 4: If intervals[j][1] <= intervals[i][0]: dp[i] = max(dp[i], dp[j] + 1).
  5. Step 5: Find max(dp) and return n - max(dp).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int eraseOverlapIntervals(vector<vector<int>>& intervals) {
10 if (intervals.empty()) return 0;
11 sort(intervals.begin(), intervals.end());
12
13 int n = intervals.size();
14 vector<int> dp(n, 1);
15 int maxKept = 1;
16
17 for (int i = 1; i < n; ++i) {
18 for (int j = 0; j < i; ++j) {
19 if (intervals[j][1] <= intervals[i][0]) {
20 dp[i] = max(dp[i], dp[j] + 1);
21 }
22 }
23 maxKept = max(maxKept, dp[i]);
24 }
25
26 return n - maxKept;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<vector<int>> intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
33 cout << "Min Removals (DP): " << sol.eraseOverlapIntervals(intervals) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N^2)
  • Space complexity: O(N)

3. Greedy Earliest End Time First

Intuition

Sort intervals ascending by end time. Keep the interval finishing earliest; whenever an interval's start is less than the current end, remove it.

Algorithm

  1. Step 1: If intervals is empty, return 0.
  2. Step 2: Sort intervals ascending by intervals[i][1].
  3. Step 3: Initialize lastEnd = intervals[0][1], removals = 0.
  4. Step 4: Iterate from i = 1 to n - 1:
  5. Step 5: If intervals[i][0] < lastEnd, increment removals (overlap detected).
  6. Step 6: Else, update lastEnd = intervals[i][1] (no overlap, keep interval).
  7. Step 7: Return removals.

Interactive Trace for Non-overlapping Intervals

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Step 1: First interval [1, 2]
Visual state
Values and pointers at this exact step
pointers
S
kept
pending
pending
pending
0
↑ current
1
2
3
Check / comparison
Initial interval kept.
Decision / next transition
lastEnd = 2.
Why this step matters

Step 1: First interval [1, 2]. Always kept. lastEnd = 2, removed = 0.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int eraseOverlapIntervals(vector<vector<int>>& intervals) {
10 if (intervals.empty()) return 0;
11 sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
12 return a[1] < b[1];
13 });
14
15 int removals = 0;
16 int lastEnd = intervals[0][1];
17
18 for (size_t i = 1; i < intervals.size(); ++i) {
19 if (intervals[i][0] < lastEnd) {
20 removals++;
21 } else {
22 lastEnd = intervals[i][1];
23 }
24 }
25
26 return removals;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<vector<int>> intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
33 cout << "Min Removals (Optimal): " << sol.eraseOverlapIntervals(intervals) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Exhaustive Subset SearchO(2^N)O(N)Generate all 2N subsets of intervals, check if the chosen subset has any overlaps, and find the subset with maximum non-overlapping elements.Subset enumeration.
2.Better — Longest Increasing Subsequence DPO(N^2)O(N)Sort intervals by start time. Let dp[i] be the maximum non-overlapping intervals ending at interval i. dp[i] = 1 + max(dp[j]) for j < i with end[j] <= start[i]. Return N - max(dp).Nested inner loop scan.
3.Optimal — Greedy Earliest End TimeOptimalO(N log N)O(1) auxiliarySort intervals ascending by end time. Keep the first interval. For each subsequent interval, if start < lastEnd, increment removals; otherwise update lastEnd = end.Sorting operation.
Back to DSA Sheet