Skip to main content

1288. Remove Covered Intervals

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

Python​

Force Busted​

  • Time: O(nlogn)
  • Space: O(1)
class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        result = len(intervals)
        for i in range(len(intervals)):
            for j in range(len(intervals)):
                if i == j or not intervals[i] or not intervals[j]:
                    continue
                if intervals[i][0] <= intervals[j][0] and intervals[i][1] >= intervals[j][1]:
                    intervals[j] = None
                    result -= 1
        return result

Sort​

  • Solution from leetcode offical
  • Sort the intervals first
    • Sort start in incremental
    • Sort end in decremental if start are the same
from functools import cmp_to_key


class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        def comp(cur, pre):
            start1, end1 = pre
            start2, end2 = cur

            if start1 == start2:
                return end1 - end2
            else:
                return start2 - start1

        intervals.sort(key=cmp_to_key(comp))

        count = 0
        prev_end = 0
        for interval in intervals:
            end = interval[1]
            if end > prev_end:
                count += 1
                prev_end = end
        return count