A LeetCode Daily Series — Day 95

Today’s problem is called "Non-overlapping Intervals"

Updated: at 05:25 AM

In this article, we will explore how to solve the problem of finding the minimum number of intervals to remove to make the rest of the intervals non-overlapping. We’ll start by understanding the problem, then discuss an efficient approach to solve it, and finally, challenge our understanding with some additional thoughts.

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

Cover Image

Understanding the Problem

Given an array of intervals where intervals[i] = [starti, endi], we need to determine the minimum number of intervals to remove to make the remaining intervals 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.

Using Efficient Approach (Greedy Algorithm)

To solve this problem efficiently, we can use a greedy algorithm. The idea is to always keep the interval with the earliest end time and remove overlapping intervals. This approach ensures that we have the maximum number of non-overlapping intervals.

def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[1])

    res = 0
    prevEnd = intervals[0][1]

    for start, end in intervals[1:]:
        if start >= prevEnd:
            prevEnd = end
        else:
            res += 1
            prevEnd = min(prevEnd, end)
    return res

Explanation

  1. Sorting:
    • We first sort the intervals based on their end times. This helps in minimizing the number of intervals to be removed by always considering the interval that finishes the earliest.
  2. Initialization:
    • We initialize res to 0, which will count the number of intervals we need to remove.
    • prevEnd is set to the end time of the first interval.
  3. Iteration:
    • We iterate over the intervals starting from the second one.
    • If the start time of the current interval is greater than or equal to prevEnd, it means the current interval does not overlap with the previous one. We update prevEnd to the end time of the current interval.
    • If there is an overlap, we increment the res counter and update prevEnd to the minimum of the current prevEnd and the end time of the current interval. This ensures we are always keeping the interval with the smallest end time to maximize the remaining non-overlapping intervals.

Time Complexity: Sorting the intervals takes O(n log n), and iterating through them takes O(n), so the overall time complexity is O(n log n).

Space Complexity: Sorting uses O(n) space, but this can be considered O(1) if we sort in place.

Results

Conclusion

In this article, we explored an efficient greedy algorithm to solve the problem of making intervals non-overlapping by removing the minimum number of intervals. We discussed the approach in detail, explained the code, and analyzed the time and space complexities.

This problem is a great example of how sorting and greedy strategies can be used to solve interval problems efficiently.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series

https://www.riteshakya.com.np/posts/a-leetcode-daily-series-day-96