986. Interval List Intersections - notruilin/LeetCode GitHub Wiki
If two closed intervals (A[i] and B[j]) have an intersection, it will be Interval(max(A[i].start, B[j].start), min(A[i].end, B[j].end))
e.g. A[i]=[1,3], B[j]=[2,4]: Interval(max(1,2), min(3,4)) = [2,3]
while i < len(A) and j < len(B):
while i < len(A) and A[i].end < B[j].start:
i += 1
if i >= len(A): break
while j < len(B) and B[j].end < A[i].start:
j += 1
if j >= len(B): break
if A[i].start > B[j].end or B[j].start > A[i].end: continue
ans.append(Interval(max(A[i].start, B[j].start), min(A[i].end, B[j].end)))
......
I try to ensure there is an intersection before append to ans in the first place, which is unnecessary.
start = max(A[i].start, B[j].start)
end = min(A[i].end, B[j].end)
if start <= end:
ans.append(Interval(start, end))
'start <= end' could ensure the intersection is legal. Then move the two pointers. Note to check i < len(A).
while i < len(A) and (A[i].end < start or A[i].end == end):
i += 1
while j < len(B) and (B[j].end < start or B[j].end == end):
j += 1
Another way is only removing the interval with the smallest endpoint.
if A[i].end < B[j].end:
i += 1
else:
j += 1