Devin's Blog

Remove Covered Intervals

3 min read

Intuition

  • By sorting by start time, we know that any interval following the ith interval would at least start at the previous interval
  • Therefore, we only have to check if the end exceeds the end of the current interval, and go to that next interval if that is the case.
    • Since any interval following the current one would have at least equal start time, but greater end time meaning more chances of overlapping with later intervals.
  • My code is elegant, but I had not considered the case where an interval that has the same start time ends earlier, and is earlier in the intervals list.
    • For example: [[1,2], [1,4], [3,4]]:
      • In this case, I have to also add 1 to the intervals removed since [1,2] is completely overlapped by [1,4].

To avoid this, you could use:

# Sort by start point.
# If two intervals share the same start point
# put the longer one to be the first.
intervals.sort(key = lambda x: (x[0], -x[1]))
  • Additionally, my method counts the overlapping intervals and subtracts from the initial amount. It is more straightforward to count the number of remaining intervals directly. To do this, count each interval that surpasses the end of the previous one, initialized at 1 since the first interval does not overlap with anything previous to it.

Complexity

  • for sorting then looping through each interval
  • space since we do not use axillary arrays

Code

Counting Remaining Intervals Directly

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x: (x[0], -x[1]))
        prev_end = 0
        res = 0 
        for _, end in intervals:
            if end > prev_end:
                prev_end = end
                res += 1
        return res

With Lambda Sort

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x: (x[0], -x[1]))
        start, end = intervals[0]
        res = 0
        for c_start, c_end in intervals[1:]:
            if c_end > end:
                start, end = c_start, c_end
            elif c_start <= end:
                res += 1
        return len(intervals) - res
  • Notice how the additional if statement comparing start == c_start was removed.

Without Sort Lambda Trick

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        n = len(intervals)
        start, end = intervals[0]
        res = 0
        for i in range(1, n):
            c_start, c_end = intervals[i]
            if c_end > end:
                if start == c_start:
                    res += 1
                start, end = c_start, c_end
            elif c_start <= end:
                res += 1
        return n - res

Notes

References

https://leetcode.com/problems/remove-covered-intervals/description/

Graph View