Naive solution
class Solution:
def removeInterval(self, A: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
"""
tc O(NlgN) sc O(N)
main idea: sweep line and check if accumutive cnt == 1 while prev cnt ==0; At this time valid pair of tart and end interval can be added into res
"""
d = collections.defaultdict(int)
for s,e in A:
d[s] += 1
d[e] -= 1
d[toBeRemoved[0]] -= 1
d[toBeRemoved[1]] += 1
cnt = 0
start = end = None
res = []
for t,v in sorted(d.items()):
if cnt + v == 1:
cnt += v
start = t
elif cnt== 1 and cnt+v == 0:
cnt += v
end = t
res.append([start,end])
start = end = None
else:
cnt += v
return res
"""
follow up with unsorted intervals and multiple toBeRemoved itervals
"""
cnt,res = 0, []
for t, v in sorted(pair for s,e in A for pair in [[s,1],[e,-1],[toBeRemoved[0],-10000],[toBeRemoved[1],10000]]):
if cnt <= 0 and cnt +v > 0 :
prev = t
elif cnt > 0 and cnt +v <= 0:
res.append([prev,t])
cnt += v
return res
optimization
class Solution:
def removeInterval(self, A: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
"""
assuming A is non-overlap and sorted order asc
tc O(N) sc O(1)
"""
res = []
for s,e in A:
del_s, del_e = toBeRemoved
#non-overlaps
if s > del_e or e< del_s:
res.append([s,e])
# overlaps
else:
if s < del_s:
res.append([s,del_s])
if e > del_e:
res.append([del_e,e])
return res
#################################################other way below ##########
start ,end = toBeRemoved
res = []
for s,e in A:
diff_s = start - s
diff_e = e - end
if diff_s > 0:
res.append([s,min(start,e)])
if diff_e > 0:
res.append([max(end,s),e])
return res