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

Remove Covered Intervals

Number: 1222

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a list of intervals, remove all intervals that are covered by another interval in the list. An interval [a, b) is covered by another interval [c, d) if and only if c <= a and b <= d. The goal is to return the number of remaining intervals after removal.

Key Insights

  • Sort intervals by their start points in ascending order and by end points in descending order when starts are equal.
  • By sorting this way, if two intervals have the same start, the longer interval comes first, making it easier to detect coverage.
  • Keep track of the maximum end encountered so far.
  • When iterating, if the current interval's end is less than or equal to the tracked maximum end, it is covered by a previous interval.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting, with an additional O(n) for a single pass through the intervals. Space Complexity: O(1) extra space if the sort is in-place.

Solution

The solution involves a greedy approach:

  1. Sort the intervals by start coordinate in ascending order; if two intervals share the same start, sort them by their end coordinate in descending order.
  2. Initialize a counter for the number of non-covered intervals and a variable to record the farthest end encountered.
  3. Iterate through the sorted list. For each interval, if its end is greater than the maximum end seen so far, it is not covered and should be counted; update the maximum end.
  4. Return the count.

This technique ensures each interval is processed only once after sorting, which yields an efficient and optimal solution.

Code Solutions

# Python solution to remove covered intervals with line-by-line comments
class Solution:
    def removeCoveredIntervals(self, intervals):
        # Sort intervals by start ascending and then by end descending.
        intervals.sort(key=lambda x: (x[0], -x[1]))
        count = 0  # Initialize counter for non-covered intervals.
        max_end = 0  # Track the maximum end encountered.

        # Iterate over the sorted intervals.
        for start, end in intervals:
            # If the current interval's end is greater than the maximum end seen,
            # it is not covered by any previous interval.
            if end > max_end:
                count += 1  # Increment count of valid intervals.
                max_end = end  # Update the maximum end.
        # Return the count of remaining intervals.
        return count

# Example usage:
sol = Solution()
print(sol.removeCoveredIntervals([[1,4],[3,6],[2,8]]))
← Back to All Questions