# Non-overlapping Intervals
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/non-overlapping-intervals)
Canonical: https://scaleengineer.com/dsa/problems/non-overlapping-intervals
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Snowflake](https://scaleengineer.com/companies/snowflake), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [Capital One](https://scaleengineer.com/companies/capital-one), [Verkada](https://scaleengineer.com/companies/verkada), [Instacart](https://scaleengineer.com/companies/instacart)
---
## Problem
Given an array of intervals `intervals` where `intervals[i] = [starti, endi]`, return _the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping_.

**Note** that intervals which only touch at a point are **non-overlapping**. For example, `[1, 2]` and `[2, 3]` are non-overlapping.

**Example 1:**

**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:**

**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.

**Example 3:**

**Input:** intervals = [[1,2],[2,3]]
**Output:** 0
**Explanation:** You don't need to remove any of the intervals since they're already non-overlapping.

**Constraints:**

* `1 <= intervals.length <= 105`
* `intervals[i].length == 2`
* `-5 * 104 <= starti < endi <= 5 * 104`

# Approaches
## Dynamic Programming
This approach uses dynamic programming, which is a common technique for optimization problems. The idea is to build up a solution by finding the optimal solution for smaller subproblems. We sort the intervals by their start times and then, for each interval, we determine the maximum number of non-overlapping intervals that can be formed ending with that interval. This is analogous to solving the Longest Increasing Subsequence problem.
**Time:** O(N^2), where N is the number of intervals. The dominant part is the nested loop used to fill the `dp` array. The initial sort takes O(N log N). · **Space:** O(N), where N is the number of intervals. This is for the `dp` array used to store intermediate results.
**Pros:** It is a systematic approach that guarantees finding the optimal solution.; The logic is a standard application of dynamic programming.
**Cons:** The O(N^2) time complexity makes it too slow for the given constraints, leading to a 'Time Limit Exceeded' error on large inputs.
### Explanation
First, we sort the intervals based on their start times. This ordering is crucial as it allows us to build our solution sequentially. We define `dp[i]` as the maximum number of compatible (non-overlapping) intervals we can select from the first `i` intervals, with the condition that the `i`-th interval must be included in our selection.

We initialize `dp[i] = 1` for all `i`, because a single interval by itself is always a valid non-overlapping set. Then, we iterate through the intervals from `i = 1` to `n-1`. For each `i`, we look back at all previous intervals `j < i`. If `intervals[j]` and `intervals[i]` are non-overlapping (i.e., `intervals[j][1] <= intervals[i][0]`), we can potentially form a longer sequence of non-overlapping intervals by appending `intervals[i]` to the sequence ending at `intervals[j]`. We update `dp[i]` to be the maximum of its current value and `1 + dp[j]`. 

After computing all `dp` values, the maximum value in the `dp` array gives the size of the largest possible non-overlapping set of intervals. The minimum number of intervals to remove is then the total number of intervals minus this maximum size.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, Comparator.comparingInt(a -> a[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], 1 + dp[j]);
                }
            }
            maxKept = Math.max(maxKept, dp[i]);
        }

        return n - maxKept;
    }
}
```
### Algorithm
- Sort the `intervals` array based on the start times of the intervals.
- Create a dynamic programming array `dp` of size `n`, where `n` is the number of intervals.
- `dp[i]` will store the maximum number of non-overlapping intervals in a sequence that ends with `intervals[i]`.
- Initialize all elements of `dp` to 1, as any single interval is a valid non-overlapping set.
- Iterate from the second interval (`i = 1`) to the end. For each `intervals[i]`, iterate through all preceding intervals `j` (from `0` to `i-1`).
- If `intervals[j]` does not overlap with `intervals[i]` (i.e., `intervals[j][1] <= intervals[i][0]`), it means `intervals[i]` can extend the non-overlapping sequence ending at `intervals[j]`. Update `dp[i]` accordingly: `dp[i] = max(dp[i], 1 + dp[j])`.
- After the loops complete, find the maximum value in the `dp` array. This value, `maxKept`, is the size of the largest set of non-overlapping intervals.
- The minimum number of intervals to remove is `n - maxKept`.

## Greedy Approach by Sorting on Start Time
A more efficient method is a greedy approach. The problem of minimizing removals is equivalent to maximizing the number of non-overlapping intervals we keep. This approach involves sorting the intervals by their start times and then iterating through them, making a locally optimal choice at each step. When an overlap is detected, we greedily decide which interval to discard to best accommodate future intervals.
**Time:** O(N log N), dominated by the initial sorting of the intervals. The subsequent linear scan takes O(N) time. · **Space:** O(log N) or O(N), depending on the space used by the sorting algorithm. In Java, `Arrays.sort` for primitives uses a dual-pivot quicksort which takes O(log N) space on average, while for objects it uses Timsort which takes O(N) space in the worst case.
**Pros:** The O(N log N) time complexity is very efficient and passes the given constraints.; It correctly solves the problem by making a locally optimal greedy choice.
**Cons:** The logic for updating the `lastEnd` during an overlap can be slightly less direct to reason about compared to the end-time sorting strategy.
### Explanation
The strategy is to process intervals in the order they begin. We sort the intervals by their start times. We then iterate through the sorted list, maintaining the end time of the last interval we decided to keep. Let's call this `lastEnd`.

We initialize `lastEnd` with the end time of the very first interval. Then, for each subsequent interval, we check if its start time is less than `lastEnd`. 

If it is, we have an overlap. We must remove one interval. The greedy choice is to remove the interval that finishes later. This is because keeping the interval that finishes earlier will free up the timeline sooner, maximizing the potential to fit more intervals later on. So, we increment our removal count and update `lastEnd` to the minimum of its current value and the end time of the current interval (effectively keeping the one that ends sooner).

If the current interval's start time is not less than `lastEnd`, there's no overlap. We can keep this interval, so we simply update `lastEnd` to the end time of this new interval.

After checking all intervals, the total count of removals is our answer.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length <= 1) {
            return 0;
        }

        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        int removals = 0;
        int lastEnd = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            // Overlap case
            if (intervals[i][0] < lastEnd) {
                removals++;
                // Greedily keep the one that ends earlier
                lastEnd = Math.min(lastEnd, intervals[i][1]);
            } else {
                // No overlap case, update the end to the current interval's end
                lastEnd = intervals[i][1];
            }
        }
        return removals;
    }
}
```
### Algorithm
- Sort the `intervals` array based on the start times of the intervals.
- If there are 1 or fewer intervals, no removals are needed, so return 0.
- Initialize a `removals` counter to 0.
- Keep track of the end point of the last interval that was kept. Initialize this `lastEnd` with the end point of the first interval (`intervals[0][1]`).
- Iterate through the sorted intervals starting from the second one (`i = 1`).
- For each `intervals[i]`, check if it overlaps with the interval corresponding to `lastEnd`. An overlap occurs if `intervals[i][0] < lastEnd`.
- If there is an overlap:
    - Increment the `removals` counter.
    - To make a greedy choice, we must discard one of the two overlapping intervals. We should keep the one that finishes earlier to leave more room for future intervals. So, we update `lastEnd = min(lastEnd, intervals[i][1])`.
- If there is no overlap (`intervals[i][0] >= lastEnd`):
    - We keep the current interval. Update `lastEnd` to the end of the current interval: `lastEnd = intervals[i][1]`.
- Return the final `removals` count.

## Greedy Approach by Sorting on End Time
This is the most efficient and canonical greedy solution for this problem. The core insight is that by sorting the intervals by their end times, we can make a simple and powerful greedy choice. At each step, we consider keeping the interval that finishes the earliest. This strategy maximizes the available time for subsequent intervals, leading to a globally optimal solution.
**Time:** O(N log N), where N is the number of intervals. The cost is dominated by the sorting step. · **Space:** O(log N) or O(N), for the space required by the sorting algorithm, similar to the other greedy approach.
**Pros:** Optimal time complexity of O(N log N).; The logic is very clean and straightforward once the greedy strategy is understood.; It is a classic and widely applicable algorithm for interval scheduling problems.
**Cons:** The correctness relies on the greedy choice proof, which might not be immediately obvious without prior exposure to activity selection problems.
### Explanation
This approach reframes the problem from 'minimum intervals to remove' to 'maximum intervals to keep'. The key idea is to always pick the interval that finishes first. Why? Because this interval frees up the resource (the timeline) as early as possible, thus maximizing the opportunity to schedule more intervals later.

First, we sort the intervals based on their end times. We then initialize a `count` of non-overlapping intervals to 1, and set a variable `end` to the end time of the first interval in the sorted list. This signifies that we are keeping the first interval.

Next, we iterate through the rest of the sorted intervals. For each interval, we check if its start time is greater than or equal to `end`. If it is, the interval doesn't overlap with the last one we kept. This makes it a valid candidate to add to our non-overlapping set. We increment `count` and update `end` to the end time of this new interval. If an interval does overlap, we simply ignore it and move on. By ignoring it, we are effectively 'removing' it because our previous choice (the one with the earlier end time) is preserved.

Finally, the number of intervals to remove is the total number of intervals minus the `count` of intervals we were able to keep.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length <= 1) {
            return 0;
        }

        // Sort by end times
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));

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

        for (int i = 1; i < intervals.length; i++) {
            // If the current interval does not overlap with the previous one we kept
            if (intervals[i][0] >= end) {
                count++;
                end = intervals[i][1];
            }
        }

        // The number of intervals to remove is total - max non-overlapping
        return intervals.length - count;
    }
}
```
### Algorithm
- If there are 1 or fewer intervals, no removals are needed, so return 0.
- Sort the `intervals` array based on the **end times** of the intervals in ascending order.
- Initialize a counter for the number of non-overlapping intervals we can keep, `count = 1`. We start with 1 because we will always keep the first interval in the sorted list.
- Initialize a variable `end` to hold the end time of the last kept interval. Set it to the end time of the first interval: `end = intervals[0][1]`.
- Iterate through the sorted intervals starting from the second one (`i = 1`).
- For each `intervals[i]`, check if it is compatible with the last kept interval. This is true if `intervals[i][0] >= end`.
- If they are compatible, it means we can keep this interval. Increment `count` and update `end` to the end time of the current interval: `end = intervals[i][1]`.
- If they are not compatible (i.e., they overlap), we do nothing. We are effectively discarding the current interval because it conflicts with our previous choice, and our previous choice (which ends earlier) is the better greedy pick.
- After the loop, `count` holds the maximum number of non-overlapping intervals. The number to remove is `n - count`.

# Solutions
### Java

```java
class Solution {
public
  int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a->a[1]));
    int t = intervals[0][1], ans = 0;
    for (int i = 1; i < intervals.length; ++i) {
      if (intervals[i][0] >= t) {
        t = intervals[i][1];
      } else {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int eraseOverlapIntervals(vector<vector<int>> &intervals) {
    sort(intervals.begin(), intervals.end(),
         [](const auto &a, const auto &b) { return a[1] < b[1]; });
    int ans = 0, t = intervals[0][1];
    for (int i = 1; i < intervals.size(); ++i) {
      if (t <= intervals[i][0])
        t = intervals[i][1];
      else
        ++ans;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: intervals . sort(key=lambda x: x[1]) ans, t = 0, intervals[0][1] for s, e in intervals[1:]: if s >= t: t = e else: ans += 1 return ans

```