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 <= 105intervals[i].length == 2-5 * 104 <= starti < endi <= 5 * 104In #435 Non-overlapping Intervals, the goal is to remove the minimum number of intervals so that the remaining intervals do not overlap. A key observation is that choosing intervals with the earliest finishing time leaves more room for future intervals, making this a classic greedy + sorting problem.
A common strategy is to first sort the intervals based on their end times. Then iterate through them while tracking the end of the last accepted interval. If the current interval overlaps with the previous one, you count it as a removal; otherwise, you update the tracking end time. This greedy choice ensures you keep as many compatible intervals as possible.
An alternative way to think about the problem is through Dynamic Programming, similar to interval scheduling or longest chain problems. However, this approach is usually less efficient than the greedy method. The greedy solution achieves optimal results with O(n log n) time due to sorting and O(1) extra space (excluding sorting overhead).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy (Sort by End Time) | O(n log n) | O(1) |
| Dynamic Programming | O(n^2) | O(n) |
NeetCode
The greedy approach involves sorting the intervals by their end times. Then, we iterate through the sorted list and count the number of overlapping intervals to remove. The idea is to always pick the interval with the earliest end time, which leaves more room for the remaining intervals.
Steps:
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1), excluding the input space for the intervals.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void
This C implementation sorts the intervals based on their end times using qsort. It then iterates through the sorted intervals, maintaining a count of the overlapping intervals to be removed and updating the end of the last included interval.
This approach utilizes dynamic programming to solve the problem. It is typically less efficient than the greedy method but serves as an illustrative illustration of tackling overlap problems using dp.
Time Complexity: O(n^2) due to nested loops for dp updates.
Space Complexity: O(n) required for the dp array.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, interval scheduling problems like Non-overlapping Intervals are commonly asked in FAANG and other top tech interviews. They test understanding of greedy algorithms, sorting, and reasoning about optimal substructure.
The optimal approach uses a greedy strategy by sorting intervals based on their end times. By always selecting the interval that finishes earliest, you maximize the number of non-overlapping intervals and minimize removals.
Sorting by end time ensures that the interval that frees up the timeline the earliest is chosen first. This greedy choice leaves maximum space for subsequent intervals and leads to the optimal solution.
Arrays or lists are typically used to store the intervals, and sorting utilities help order them by end time. Only simple variables are needed to track the previous interval’s end during iteration.
Java's dynamic programming approach similarly initializes the dp table and sorts intervals by start time. The nested loop checks intervals for compatibility of non-overlapping arrangement and updates maximum possible count found.