Remove Covered Intervals - Leetcode Solution

Problem:

Given a list of intervals, remove all intervals that are covered by another interval in the list. Interval [a,b) is covered by interval [c,d) if and only if c <= a and b <= d. After doing so, return the number of remaining intervals.

Example:

Input: intervals = [[1,4],[3,6],[2,8]] Output: 2 Explanation: Interval [3,6] is covered by [2,8], therefore it is removed and the remaining intervals are [1,4] and [2,8].

Solution:

We can solve this problem by sorting the intervals in ascending order based on their beginning value and then iterate through the sorted intervals. We will use two pointers to keep track of the current interval and the one that we compare it with. If the current interval is covered by the compared interval, we skip it and continue to the next one. Otherwise, we keep the current interval and update the compared interval to the next one.

Here is the detailed step-by-step solution:

1. Sort the input intervals in ascending order based on their beginning value. We can use Python's built-in sorted() function to do this.

   intervals = sorted(intervals, key=lambda x: x[0])
   

2. Initialize a variable count to keep track of the remaining intervals. Set it to 1 because we will always keep the first interval.

   count = 1
   

3. Initialize two variables, prev_beginning and prev_ending, to the beginning and ending values of the first interval.

   prev_beginning, prev_ending = intervals[0]
   

4. Loop through the remaining intervals, starting from the second one.

   for i in range(1, len(intervals)):
   

5. For each interval, compare its beginning and ending values with the previous interval.

   beginning, ending = intervals[i]
   if prev_beginning <= beginning and ending <= prev_ending:
       # The current interval is covered by the previous one, so skip it.
       continue
   

6. If the current interval is not covered by the previous one, update prev_beginning and prev_ending to the values of the current interval and increment count by 1.

   prev_beginning, prev_ending = beginning, ending
   count += 1
   

7. Return the final value of count.

   return count
   

Here is the Python code:

def removeCoveredIntervals(intervals: List[List[int]]) -> int: # Sort the intervals in ascending order based on their beginning values intervals = sorted(intervals, key=lambda x: x[0]) # Initialize count to 1 because we will always keep the first interval count = 1 # Initialize variables to the beginning and ending values of the first interval prev_beginning, prev_ending = intervals[0] # Loop through the remaining intervals for i in range(1, len(intervals)): # Compare the current interval with the previous one beginning, ending = intervals[i] if prev_beginning <= beginning and ending <= prev_ending: # The current interval is covered by the previous one, so skip it continue # The current interval is not covered by the previous one, so update variables and increment count prev_beginning, prev_ending = beginning, ending count += 1 # Return the final count return count

Time Complexity: O(nlogn) (sorting takes O(nlogn) time and the loop takes O(n) time)

Space Complexity: O(1) (we don't use any extra data structures)

1