We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Non-overlapping Intervals

Difficulty: Medium

Problem Description

Given an array of intervals where intervals[i] = [start_i, end_i], 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.

Key Insights

  • To make the intervals non-overlapping, we need to minimize the number of overlapping intervals.
  • A greedy approach can be used by selecting intervals based on their end times.
  • Sorting the intervals by their end times allows us to efficiently determine which intervals can be kept without overlap.

Space and Time Complexity

Time Complexity: O(n log n), due to the sorting step.
Space Complexity: O(1), since we are modifying the input in place and using a few additional variables for counting.

Solution

The problem can be solved using a greedy algorithm. First, we sort the intervals based on their end times. Then, we iterate through the sorted list and keep track of the end of the last added interval. For each interval, if its start time is less than the end time of the last added interval, it means there is an overlap, and we increment our removal count. Finally, the result will be the total number of intervals minus the number of intervals we were able to keep.

Code Solutions

def eraseOverlapIntervals(intervals):
    if not intervals:
        return 0

    # Sort the intervals by their end time
    intervals.sort(key=lambda x: x[1])
    count = 0
    end = intervals[0][1]

    for i in range(1, len(intervals)):
        if intervals[i][0] < end:  # There is an overlap
            count += 1  # We need to remove this interval
        else:
            end = intervals[i][1]  # Update the end time to the current interval's end

    return count
← Back to All Questions