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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Non-overlapping Intervals

Number: 435

Difficulty: Medium

Paid? No

Companies: Amazon, Meta, Microsoft, Zoho, Bloomberg, Capital One, Verkada, J.P. Morgan, Apple, Google, Oracle, TikTok

Problem Description

Given an array of intervals where each interval is represented as [start, end], the goal is to remove the minimum number of intervals so that the remaining intervals do not overlap. Note that intervals that only touch (i.e. end of one equals start of the other) are considered non-overlapping.

Key Insights

  • Sorting is the key: By sorting intervals by their end times, we can greedily choose the optimal set of non-overlapping intervals.
  • Greedy approach: Always select the interval that ends the earliest, as it leaves maximum room for subsequent intervals.
  • Counting removals: The answer is the total number of intervals minus the count of intervals selected by this greedy approach.
  • Edge observation: Intervals that touch at the boundary are not overlapping, so the check uses “>=” instead of “>”.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the intervals. Space Complexity: O(n) if considering the storage for the sorted list (or O(1) if sorting in-place).

Solution

The solution involves first sorting the intervals by their end times. Initialize a variable to track the end of the last chosen interval. Iterate over the sorted intervals: if the current interval’s start is greater than or equal to the last chosen interval’s end, update the last end and include this interval in the non-overlapping set. Otherwise, count the interval as one that must be removed. The final answer is the removal count, which is computed as the total number of intervals minus the count of non-overlapping intervals selected.

Code Solutions

# Python implementation for Non-overlapping Intervals

def eraseOverlapIntervals(intervals):
    # Sort intervals based on the end time
    intervals.sort(key=lambda x: x[1])
    
    # Initialize the count of intervals in the non-overlapping set
    count = 0
    # Initialize the end of the last added interval to the minimum possible value
    last_included_end = float('-inf')
    
    # Iterate over every interval in the sorted list
    for interval in intervals:
        # If the current interval does not overlap with the last added interval
        if interval[0] >= last_included_end:
            count += 1           # We include this interval
            last_included_end = interval[1]  # Update end for subsequent comparisons
    # The minimum number of removals is total intervals minus non-overlapping intervals count
    return len(intervals) - count

# Example usage:
print(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]]))  # Expected output: 1
← Back to All Questions