Skip to content
AI360Xpert
Back to Intervals
Medium

Non-overlapping Intervals

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.

Examples

Input:intervals = [[1,2],[2,3],[3,4],[1,3]]
Output:1
[1,3] can be removed and the rest of the intervals are non-overlapping.
Input:intervals = [[1,2],[1,2],[1,2]]
Output:2
You need to remove two [1,2] to make the rest of the intervals non-overlapping.
Input:intervals = [[1,2],[2,3]]
Output:0
You don't need to remove any of the intervals since they're already non-overlapping.

Constraints

  • 1 <= intervals.length <= 10^5
  • intervals[i].length == 2
  • -5 * 10^4 <= starti < endi <= 5 * 10^4

Greedy (Sort by End Time)

Approach

To minimize the number of intervals removed, we want to keep as many non-overlapping intervals as possible. The best way to leave room for future intervals is to always pick the interval that ends earliest. So, we sort the intervals by their end times. We keep track of the `end` time of the last added interval. For each subsequent interval, if its start time is greater than or equal to `end`, it does not overlap. We update `end` to this interval's end time. If it overlaps (start time < `end`), we must remove it, so we increment our removal counter.

Complexity Analysis

Time Complexity
O(n log n)
Space Complexity
O(1)

Time complexity is O(n log n) because of sorting. The iteration takes O(n). Space complexity is O(1) assuming sorting is done in-place, or O(n) depending on the sorting algorithm implementation.

Solution.java
class Solution {    public int eraseOverlapIntervals(int[][] intervals) {        if (intervals.length == 0) return 0;                // Sort by end time        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));                int count = 0;        int end = intervals[0][1];                for (int i = 1; i < intervals.length; i++) {            if (intervals[i][0] >= end) {                // Non-overlapping, update end                end = intervals[i][1];            } else {                // Overlapping, need to remove                count++;            }        }                return count;    }}