# 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