Non Overlapping Intervals Leetcode Problem 435 [Python Solution]

Welcome to another coding tutorial! In this one, we will solve the “Non-Overlapping Intervals” problem, a part of the Blind 75 list of LeetCode questions.

If you’re new to interval-related problems, this one might seem a bit challenging at first.

However, we’ll break it down and walk you through an efficient Python solution.

Problem Overview

Given an array of intervals, each represented as [start, end], our goal is to determine the minimum number of intervals we need to remove to make sure that the remaining intervals don’t overlap.

This problem is a classic example of interval scheduling.

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] intervals to make the rest 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 <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

Now, let’s dive into the problem, understand the constraints, and explore both brute-force and efficient approaches to solving it.

Problem Overview

To solve the “Non-Overlapping Intervals” problem, we need to remove the minimum number of intervals to ensure that the rest of the intervals do not overlap.

Let’s start by understanding what it means for intervals to overlap.

Two intervals [a, b] and [c, d] overlap if a < d and c < b.

If the start of one interval is less than the end of the other, they overlap.

Example 1:

Let’s consider an example to illustrate the problem:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

We have four intervals.

When visualized, they look like this:

[1,2] | [2,3] | [3,4] | [1,3]

As you can see, the interval [1,3] overlaps with [1,2], and the other intervals do not overlap.

Our task is to remove as few intervals as possible to make the remaining ones non-overlapping.

Understanding Constraints

The constraints provided are crucial for understanding the problem’s complexity and performance.

Here’s what they mean:

• 1 <= intervals.length <= 105: The input can have a maximum of 105 intervals, which implies that we need an efficient solution.
• intervals[i].length == 2: Each interval is represented by two values, start and end.
• -5 * 104 <= starti < endi <= 5 * 104: The start and end values of each interval fall within this range.

This provides some bounds for the values we’re dealing with.

Now, let’s explore two approaches to solving this problem: the brute-force approach and the efficient approach.

We’ll also provide Python code for each.

Non Overlapping Intervals LeetCode Problem Solution

1. Bruteforce Approach

A brute-force approach involves trying out all possible combinations of intervals and counting the minimum number of removals required to make the remaining intervals non-overlapping.

def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    intervals.sort()  # Sort the intervals by start values
    res = 0
    prevEnd = intervals[0][1]

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

    return res

In this solution, we first sort the intervals based on their start values.

Then, we iterate through the sorted intervals, comparing adjacent pairs to check if they overlap.

If two intervals overlap, we choose to remove the one with the larger end value to minimize future overlaps.

The time complexity of this brute-force approach is O(n log n) due to the sorting step, where ‘n’ is the number of intervals.

The subsequent iteration is linear, making it an efficient solution for the given constraints.

2. An Efficient Approach with Greedy Algorithm

The brute-force approach works well for this problem, but we can optimize it further using a greedy algorithm.

Instead of comparing all possible combinations of intervals, we can use a greedy strategy to select the intervals we want to keep.

In the efficient approach, we’ll follow these steps:

1. Sort the intervals by their start values in ascending order.
2. Initialize a variable res to keep track of the number of intervals to remove.
3. Initialize a variable prevEnd to store the end value of the first interval.
4. Iterate through the remaining intervals:

• If the start value of the current interval is greater than or equal to prevEnd, update prevEnd to the end value of the current interval.
• If the start value is less than prevEnd, increment res by 1 and update prevEnd to the minimum of the current interval’s end value and prevEnd.

1. Return the value of res, which represents the minimum number of intervals to remove.

Here’s the Python code for this efficient approach:

def eraseOverlapIntervals(self, intervals: List[List[int]) -> int:
    intervals.sort()  # Sort the intervals by start values
    res = 0
    prevEnd = intervals[0][1]

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

    return res

This approach has a time complexity of O(n log n) due to the sorting step, making it suitable for the given constraints.

It’s a more elegant and efficient solution than the brute-force approach.

Python Code Solution

Now that we’ve discussed the efficient approach, here’s the Python code for solving the “Non-Overlapping Intervals” problem:

def eraseOverlapIntervals(self, intervals: List[List[int]) -> int:
    intervals.sort()  # Sort the intervals by start values
    res = 0
    prevEnd = intervals[0][1]

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

    return res

This code sorts the intervals by their start values, efficiently identifies overlapping intervals, and returns the minimum number of removals required to make the remaining intervals non-overlapping.

Time and Space

Complexity

Now, let’s analyze the time and space complexity of our efficient solution:

• Time Complexity: O(n log n) – The dominant factor is the sorting step, which takes O(n log n) time, where ‘n’ is the number of intervals.

The subsequent iteration is linear, making it efficient for the given constraints.

• Space Complexity: O(1) – We use a constant amount of extra space to store variables such as res and prevEnd.

This space usage is independent of the input size.

Reasoning Behind Our Approach

The reasoning behind our efficient approach lies in the greedy strategy of selecting intervals.

By sorting the intervals by their start values and iteratively choosing intervals based on their end values, we maximize the number of non-overlapping intervals while minimizing removals.

The key insight is to always keep the interval with the smallest end value to prevent future overlaps.

Related Interview Questions By Company:

• Maximum Twin Sum Of A Linked List LeetCode
• Continuous Subarray Sum LeetCode
• Find The Duplicate Number LeetCode

Related Interview Questions By Difficulty:

• Meeting Rooms LeetCode
• Insert Interval LeetCode
• Meeting Rooms II LeetCode

Related Interview Questions By Category:

• Insertion Sort List LeetCode
• Encode And Decode Tinyurl LeetCode
• Reverse Linked List II LeetCode

Conclusion

In this blog post, we tackled the “Non-Overlapping Intervals” problem, a LeetCode question that falls under the category of intervals.

We discussed the problem’s details, constraints, and provided both a brute-force and an efficient approach to solve it.

The efficient approach, based on a greedy algorithm, offers a time complexity of O(n log n) and is suitable for the given constraints.

We hope this tutorial has been helpful in understanding the problem and its solution.

If you have any questions, suggestions, or comments, please feel free to share them in the comments section below.

Your feedback and engagement are highly valued!

Question Link

Don’t forget to like, engage, and share this content with others who might find it beneficial.

Happy coding!