Remove Covered Intervals - Leetcode 1288 - Python

0:00 - Read the problem
1:45 - Drawing Explanation
9:12 - Coding Explanation

leetcode 1288

#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[Raymond-Wu]

Love that you're doing the Leetcode dailies! I finished this a couple hours ago but it's great to see your method of thinking and doing problems

[niazahmad]

As the intervals are already sorted the `if prevL <= L ` conditions seems extra.

[UK-sfvd]

So i did it almost similar to this, but instead of saving the intervals in res, instead what i did is to update a single interval variable, which reduces space complexity by a lot.

[hen]

I like your videos, I have been following up for the last 6 months and you are already a fam now. I suggest that you make your code more explicit and longer, instead of clear and concise so that beginner can learn easily.

[ankurbhambri]

Excellent Explanation you're doing a great job please keep on doing it.

[numberonep]

Using a more classic neetcode style for a similar perf:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x : x[0], reverse=True)
stack = []
for j in range(len(intervals)):
while stack and
stack.pop()
stack.append(intervals[j])
return len(stack)

[harishsn]

class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key = lambda x:(x[0], -x[1]))
count = len(intervals)

c, d = intervals[0]
for i in range(1, len(intervals)):
a, b = intervals[i]

if (c <= a and d >= b):
count -= 1
else:
c = a
d = b

return count

[yustas]

I don't think that you need that list and additional memory.
You need just 1 pointer to the last uncovered element

class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
A = sorted(intervals, key=lambda x: (x[0], -x[1]))
L, R = A[0]
res=1
for v in A[1:]:
if not(L<=v[0] and R>=v[1]):
L, R = v
res+=1
return res
faster than 97.30% of Python3

[jayeshnagarkar]

class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort()
prevStart, prevEnd = intervals[0][0], intervals[0][1]
count = 0

for start, end in intervals[1:]:
if prevEnd >= end or (start == prevStart and end >= prevEnd):
prevEnd = max(end, prevEnd)
count = count + 1
else:
prevStart = start
prevEnd = end

return len(intervals) - count

[LordXavier]

doesnt sort funtion will use looping within to sort the array, so it is still n2 time complexity

[ArjunSurendra]

Can you solve 395. Longest Substring with At Least K Repeating Characters, it has many solutions and each one is confusing.
Your explanations are really good.

[VarunMittal-viralmutant]

A more efficient solution, without extra memory:

def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda range: (range[0], -range[1]))
last_interval = intervals[0]
remove = 0
for range in intervals[1:]:
if range[1] <= last_interval[1]:
remove += 1
else:
if range[1] > last_interval[1]:
last_interval = range
return len(intervals) - remove

[alwinjohn]

What Software tools are you using to write/draw and make videos?

[Nick-uobi]

Please introduce DSA and DP playlist it will help alot of us.

[memeproductions]

Hi! What software do you use to draw?in a real remote interview would you be asked to draw(it certainly would help you) and with what software?

[VerticalWit]

I solved it the same way yesterday in C++ but got about 20% CPU and memory scores... I am confused

[SudiptaKarmakar]

Huh, initially I thought, hold on, this wont work for cases like - [[1, 4], [2, 6], [4, 8]]. Here, [2, 6] is covered by the others combined. So, a better approach would be creating a contiguous timeline and look for missing segments - something like that. Then I re-read the problem description - "remove all intervals that are covered by **another interval** in the list" - "another interval", not multiple intervals.