LeetCode: 1288. Remove Covered Intervals

Problem

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