In this guide, you will get 435. Non-overlapping Intervals LeetCode Solution with the best time and space complexity. The solution to Non-overlapping Intervals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
435. Non-overlapping Intervals LeetCode Solution in C++
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty())
return 0;
ranges::sort(intervals,
[](const auto& a, const auto& b) { return a[1] < b[1]; });
int ans = 0;
int currentEnd = intervals[0][1];
for (int i = 1; i < intervals.size(); ++i)
if (intervals[i][0] >= currentEnd)
currentEnd = intervals[i][1];
else
++ans;
return ans;
}
}; /* code provided by PROGIEZ */
435. Non-overlapping Intervals LeetCode Solution in Java
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0)
return 0;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int ans = 0;
int currentEnd = intervals[0][1];
for (int i = 1; i < intervals.length; ++i)
if (intervals[i][0] >= currentEnd)
currentEnd = intervals[i][1];
else
++ans;
return ans;
}
} // code provided by PROGIEZ
435. Non-overlapping Intervals LeetCode Solution in Python
class Solution:
def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
ans = 0
currentEnd = -math.inf
for interval in sorted(intervals, key=lambda x: x[1]):
if interval[0] >= currentEnd:
currentEnd = interval[1]
else:
ans += 1
return ans # code by PROGIEZ
