Non-overlapping Intervals
Problem Description
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: 0Explanation: 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
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
The initial approach involves checking each pair of intervals to determine if they overlap. If an overlap is detected, remove one of the intervals and continue. This method, while straightforward, is not efficient, especially for large inputs, as it involves comparing each interval with every other interval.
Steps:
- Sort the intervals based on the starting point.
- Use two nested loops. The outer loop picks an interval, and the inner loop checks for overlaps with subsequent intervals.
- If an overlap is found, increment a counter to indicate a removal.
- Remove the interval that ends later to increase the chance of allowing future intervals to fit without overlap.
Code:
- Time Complexity: O(n^2), as we may compare each pair of intervals.
- Space Complexity: O(n) due to sorting and temporary data structures.
2. Optimized Greedy Approach
Intuition:
An improved approach leverages a greedy algorithm. By sorting intervals by their end time and then iterating through them, we can quickly identify and count needs for removal, aiming to minimize the number of intervals removed while maximizing the number of non-overlapping intervals.
Steps:
- Sort the intervals by the end time to efficiently find the optimal position to 'cut' the intervals.
- Initialize a counter for removals and set a variable for the end of the last added interval.
- Traverse the sorted intervals and check if the current interval overlaps with the last non-overlapping interval.
- If overlapped, increment the removal counter; otherwise, update the end point to the current interval’s end time.
Code:
- Time Complexity: O(n log n), mainly due to the sorting step.
- Space Complexity: O(1), as we are using only a constant amount of extra space.