Problem Statement:
Given an array of intervalsintervals 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 <= 105intervals[i].length == 2-5 * 104<= starti < endi <= 104
Approach:
- Sort intervals by end time → This ensures we always keep the interval that finishes earliest.
- Track the end of the last chosen interval
(k)→ Start with-Infinity. - Iterate over intervals:
- If the current interval starts before
k, it overlaps → incrementremoveCount(we “remove” this one). - Else, update
kto the current interval’s end (keep it).
- If the current interval starts before
- Return the total
removeCount.
Time & Space Complexity:
Time Complexity: O(n log n)
Space Complexity: O(1)
Dry Run
Input: arr = [[1,2],[2,3],[3,4],[1,3]]
Step 0: Start Function: eraseOverlapIntervals(arr) arr = [[1,2],[2,3],[3,4],[1,3]] removeCount = 0 k = -Infinity ------------------------------------------------------------ Step 1: Sort intervals by end (arr.sort((a,b) => a[1] - b[1])) Compare ends: 2,3,4,3 → sorted order (one valid result): arr = [[1,2], [2,3], [1,3], [3,4]] // intervals ordered by their end values ------------------------------------------------------------ Step 2: Iterate through sorted intervals Iteration (i = 0, interval = [1,2]): Check if arr[0][0] < k → 1 < -Infinity ? false else -> k = arr[0][1] = 2 removeCount = 0 Current k = 2 Iteration (i = 1, interval = [2,3]): Check if arr[1][0] < k → 2 < 2 ? false (strict <) else -> k = arr[1][1] = 3 removeCount = 0 Current k = 3 Iteration (i = 2, interval = [1,3]): Check if arr[2][0] < k → 1 < 3 ? true -> ++removeCount => removeCount = 1 (k remains 3) Iteration (i = 3, interval = [3,4]): Check if arr[3][0] < k → 3 < 3 ? false else -> k = arr[3][1] = 4 removeCount = 1 Current k = 4 ------------------------------------------------------------ Step 3: End Final removeCount = 1
Output: 1
var eraseOverlapIntervals = function(arr) {
arr.sort((a, b) => (a[1] - b[1]));
let removeCount = 0;
let k = -Infinity;
for(let i=0; i < arr.length; i++){
if(arr[i][0] < k){
++removeCount;
} else {
k = arr[i][1];
}
}
return removeCount;
};
def eraseOverlapIntervals(arr):
if not arr:
return 0
arr.sort(key=lambda x: x[1])
removeCount = 0
k = float('-inf')
for start, end in arr:
if start < k:
removeCount += 1
else:
k = end
return removeCount
import java.util.Arrays;
public class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals == null || intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int removeCount = 0;
int k = Integer.MIN_VALUE;
for (int[] iv : intervals) {
if (iv[0] < k) {
++removeCount;
} else {
k = iv[1];
}
}
return removeCount;
}
}
#include <vector>
#include <algorithm>
#include <limits>
int eraseOverlapIntervals(std::vector>& intervals) {
if (intervals.empty()) return 0;
std::sort(intervals.begin(), intervals.end(),
[](const std::vector& a, const std::vector& b){
return a[1] < b[1];
});
int removeCount = 0;
int k = std::numeric_limits::min(); // acts like -Infinity for ints
for (const auto &iv : intervals) {
if (iv[0] < k) {
++removeCount;
} else {
k = iv[1];
}
}
return removeCount;
}
#include <stdlib.h>
#include <limits.h>
typedef struct {
int start;
int end;
} Interval;
int cmp_end(const void *a, const void *b) {
Interval *ia = (Interval*)a;
Interval *ib = (Interval*)b;
if (ia->end < ib->end) return -1;
if (ia->end > ib->end) return 1;
return 0;
}
int eraseOverlapIntervals(Interval *arr, int n) {
if (n == 0) return 0;
qsort(arr, n, sizeof(Interval), cmp_end);
int removeCount = 0;
int k = INT_MIN;
for (int i = 0; i < n; ++i) {
if (arr[i].start < k) {
++removeCount;
} else {
k = arr[i].end;
}
}
return removeCount;
}
using System;
public class Solution {
public int EraseOverlapIntervals(int[][] intervals) {
if (intervals == null || intervals.Length == 0) return 0;
Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
int removeCount = 0;
int k = Int32.MinValue;
foreach (var iv in intervals) {
if (iv[0] < k) {
++removeCount;
} else {
k = iv[1];
}
}
return removeCount;
}
}
1 Comment
Double chance