LeetCode: 1288. Remove Covered Intervals

Problem

1288. Remove Covered Intervals

Solutions

Naive O(n²) solution

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        ret = 0
        def good(i, s, e):
            for ii, (ss, ee) in enumerate(intervals):
                if ii == i:continue
                if s>=ss and e<=ee:return False
            return True
        for i, (s, e) in enumerate(intervals):
            if good(i, s, e):
                ret += 1
        return ret

O(n log n) sorting solution

Explanation:

I am sorting it by end and when end is equal, sort by the start reversely.

For example,

[[1,4],[3,6],[2,8]]

It is already sorted by the end.

We maintain a list that contains the smallest start value when looking from right to left. Name it as min_starts, we will have

for [2, 8]

min_starts = [2]

for [[3, 6], [2, 8]]

min_starts = [2, 2]

for [[1, 4], [3, 6], [2, 8]]

min_starts = [1, 2, 2]

Then

for [1, 4], check the min_starts[1] to see whether the min_starts[1] ≤ 1, if so, [1, 4] can be removed as for all the future elements, it has end ≥ 4 and it has some interval which has a begin ≤ 1.

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        N = len(intervals)
        if N == 1: return 1
        intervals.sort(key = lambda x : (x[1], -x[0]))
        min_starts = [0]*N
        min_starts[-1] = intervals[-1][0]
        for i in range(N-2, -1, -1):
            min_starts[i] = min(intervals[i][0], min_starts[i+1])
        ret = 0
        for i, (start, end) in enumerate(intervals[:-1]):
            if start >= min_starts[i+1]:ret += 1
        if intervals[-1] == intervals[-2]:
            ret += 1
        return N - ret