# 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`

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi