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 <= 10^5
intervals[i].length == 2
-5 * 10^4 <= starti < endi <= 5 * 10^4

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

1c:Tdec,

Method 1 - Sorting by Start of Interval

We can sort the intervals based on their starting times. Track prevEnd from the previous interval. When comparing two intervals, consider the smaller end value to minimize overlaps with subsequent intervals.

Code

[{"language":"Java","code":"public class Solution {\n    public int eraseOverlapIntervals(int[][] intervals) {\n        // Sort intervals by their start times\n        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));\n\n        int prevEnd = intervals[0][1];\n        int count = 0;\n        \n        for (int i = 1; i < intervals.length; i++) {\n            if (prevEnd > intervals[i][0]) {\n                count++;\n                prevEnd = Math.min(intervals[i][1], prevEnd);\n            } else {\n                prevEnd = intervals[i][1];\n            }\n        }\n        \n        return count;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n        # Sort intervals by their start times\n        intervals.sort(key=lambda x: x[0])\n        \n        prev_end = intervals[0][1]\n        count = 0\n        \n        for i in range(1, len(intervals)):\n            if prev_end > intervals[i][0]:\n                count += 1\n                prev_end = min(intervals[i][1], prev_end)\n            else:\n                prev_end = intervals[i][1]\n        \n        return count","lang":"python"}]

Complexity

⏰ Time complexity: O(n log n) for sorting the intervals.
🧺 Space complexity: - O(1) for space as we use a constant amount of extra space (excluding input).

Method 2 - Sorting by End of Interval

Actually, the problem is similar to classic greedy problem - Interval Scheduling Problem where we are given a collection of intervals, find the maximum number of intervals that are non-overlapping".

Code

[{"language":"Java","code":"public class Solution {\n    public int eraseOverlapIntervals(int[][] intervals) {\n        if (intervals.length == 0) {\n            return 0;\n        }\n\n        // Sort intervals by their end times\n        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));\n\n        int end = intervals[0][1];\n        int count = 1;\n\n        for (int i = 1; i < intervals.length; i++) {\n            if (intervals[i][0] >= end) {\n                end = intervals[i][1];\n                count++;\n            }\n        }\n\n        return intervals.length - count;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n        if not intervals:\n            return 0\n\n        # Sort intervals by their end times\n        intervals.sort(key=lambda x: x[1])\n\n        end = intervals[0][1]\n        count = 1\n\n        for i in range(1, len(intervals)):\n            if intervals[i][0] >= end:\n                end = intervals[i][1]\n                count += 1\n        \n        return len(intervals) - count","lang":"python"}]

Complexity

⏰ Time complexity: O(n log n) for sorting the intervals.
🧺 Space complexity: O(1) as only a constant amount of extra space

Related Tags