Course4all
Join us on telegram
Home/dsa/Greedy/Non-overlapping Intervals

Non-overlapping Intervals

Master this topic with zero to advance depth.

Non-overlapping Intervals

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.

Visual Representation

Intervals: [[1,2], [2,3], [3,4], [1,3]] 1--2 2--3 3--4 1-----3 To keep most intervals (3), we must remove [1,3]. Result: 1
Medium

Examples

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1

[1,3] can be removed and the rest of intervals are non-overlapping.

Approach 1

Level I: Recursive Selection (Brute Force)

Intuition

The problem asks for the minimum removals to remove all overlaps. This is equivalent to finding the maximum number of non-overlapping intervals. We can generate all combinations of intervals (take it or leave it) and find the maximum valid set.

Thought Process

  1. Sort the intervals by start time so we can easily check for overlaps sequentially.
  2. For each interval at currIndex, we have two choices:
    • Include it: Only possible if it doesn't overlap with the last included interval prevIndex (i.e., intervals[prevIndex].end <= intervals[currIndex].start). We add 1 to our count and move to currIndex + 1.
    • Exclude it: We move to currIndex + 1 without adding to our count.
  3. Return the maximum of these two choices for all steps.
⏱ O(2^N)💾 O(N)

Detailed Dry Run

intervalsSorted = [[1,2], [1,3], [2,3]]

  • solve(-1, 0):
    • Take [1,2]: 1 + solve(0, 1) -> 1 + 1 (takes [2,3]) = 2
    • Leave [1,2]: solve(-1, 1) -> max(take[1,3], leave[1,3]) = 1 Max kept = 2. Removals = 3 - 2 = 1.
java
import java.util.Arrays;

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        return intervals.length - solve(intervals, -1, 0);
    }
    
    private int solve(int[][] intervals, int prevIndex, int currIndex) {
        if (currIndex == intervals.length) return 0;
        
        int taken = 0;
        if (prevIndex == -1 || intervals[prevIndex][1] <= intervals[currIndex][0]) {
            taken = 1 + solve(intervals, currIndex, currIndex + 1);
        }
        int notTaken = solve(intervals, prevIndex, currIndex + 1);
        
        return Math.max(taken, notTaken);
    }
}
Approach 2

Level II: Dynamic Programming (LIS Variation)

Intuition

This problem is equivalent to finding the Longest Chain of Pairs or the Longest Increasing Subsequence. We want to find the maximum number of intervals k that can be kept. Then the result is N - k.

Thought Process

  1. Sort the intervals by start time.
  2. Create a dp array where dp[i] is the maximum number of non-overlapping intervals ending at index i.
  3. For each i, look at all j < i. If intervals[j].end <= intervals[i].start, then we can extend the chain: dp[i] = max(dp[i], dp[j] + 1).

Pattern: Dynamic Programming / LIS

⏱ O(N^2)💾 O(N)

Detailed Dry Run

intervalsSorted = [[1,2], [1,3], [2,3]], dp=[1,1,1]

  • i=1 [1,3]: j=0 [1,2] overlaps. dp[1]=1.
  • i=2 [2,3]: j=0 [1,2] no overlap. dp[2]=max(1, dp[0]+1)=2.
  • i=2 [2,3]: j=1 [1,3] overlaps. dp[2]=2. Max kept = 2. Removals = 3 - 2 = 1.
java
import java.util.Arrays;

public 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 maxKept = 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);
                }
            }
            maxKept = Math.max(maxKept, dp[i]);
        }
        return n - maxKept;
    }
}
Approach 3

Level III: Optimal Greedy (Sort by End)

Intuition

To keep the maximum number of intervals, we should always pick the interval that ends the earliest. This is the classic Interval Scheduling problem. Why? Because an earlier end time leaves the most possible room for subsequent intervals.

Thought Process

  1. Sort by end point.
  2. Keep track of the lastEnd time of the last accepted interval.
  3. For each interval:
    • If start >= lastEnd, accept it and update lastEnd.
    • Else, it overlaps; increment removals count.

Pattern: Interval Scheduling

⏱ O(N log N) for sorting.💾 O(log N) or O(N) for sorting stack.

Detailed Dry Run

intervals = [[1,2], [2,3], [3,4], [1,3]] After Sort: [[1,2], [2,3], [1,3], [3,4]]

StepIntervalRangelastEndAction
1[1, 2][1, 2]2Keep [1,2]. lastEnd = 2
2[2, 3][2, 3]32 >= 2? YES. Keep [2,3]. lastEnd = 3
3[1, 3][1, 3]31 < 3? NO. Remove [1,3].
4[3, 4][3, 4]43 >= 3? YES. Keep [3,4]. lastEnd = 4

Result: 1 removal.

java
import java.util.Arrays;

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        
        // Sort by end points to maximize room for future intervals
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 1; // Count of non-overlapping intervals kept
        int lastEnd = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= lastEnd) {
                count++;
                lastEnd = intervals[i][1];
            }
        }
        return intervals.length - count;
    }
}
← Previous QuestionMinimum Number of Arrows to Burst Balloons
Next Question →Queue Reconstruction by Height