# FB Phone interview Question: Given two lists of intervals, return the intervals that overlap between the two lists.

• You are given two lists of intervals, A and B.

In A, the intervals are sorted by their starting points. None of the intervals within A overlap.

Likewise, in B, the intervals are sorted by their starting points. None of the intervals within B overlap.

Return the intervals that overlap between the two lists.

Example:

A: {[0,4], [7,12]}
B: {[1,3], [5,8], [9,11]}
Return:

{[1,3], [7,8], [9,11]}

How would you do this?

• Think of it this way, what were to happen if you instead had one list of intervals that was sorted?
You would have:
[0,4], [1,3], [5,8], [7,12], [9,12]

Your logic would compare two adjacent intervals with their starting points. Is the second intervals's starting point less than the first interval's ending point? If yes, then which interval's end point is the min? That would create your result. Continue moving down the sorted list.

In the case of this question, you already have two sorted lists, so you would have to create some logic to keep track. Remember the question wants the overlap BETWEEN the two lists. In the above example, it so happens that when you merge the list, it neatly interweaves between each other, A then B then A then B etc... You have to take into account that a list could have the first X sorted intervals and the other list have the last Y sorted intervals. Therefore, creating no results or one result if the last interval of the first list intersects with the first interval of the second.

• You can get some inspiration from "732. My Calendar III". Basically you can merge the two lists into one, where start of the interval holds +1 and end of the interval holds -1. Then if we scan the list from the beginning, we maintain how many intervals are we seeing for the moment. We emit the interval when the number we maintain becomes 2.

• This is a direct question on Leetcode, Merge Intervals.

• We can mimic merge sort. Set a current interval to be the interval with smallest start. If the next smallest interval has intersection with the current interval, get the intersection and add to result. Update the current if the next interval has a larger end.

Python code

``````def mergeInterval(L1, L2):
cur = None
res = [ ]
i, j = 0, 0
while i < len(L1) or j < len(L2):
T = None
if j == len(L2) or (i < len(L1) and L1[i].start < L2[j].start):
T = L1[i]
i += 1
else:
T = L2[j]
j += 1
if cur and T.start <= cur.end and T.end >= cur.start:
res.append(Interval(max(T.start,cur.start),min(T.end,cur.end))
if cur == None or T.end >= cur.end:
cur = T
return res
``````

• [1,3], [5,8], [9,11]
Here is a program for doing the same:

``````#!/usr/bin/env python

def mergeLists(L1 , L2):
len1 = len(L1)
len2 = len(L2)
index1 = 0
index2 = 0
pickx = 0
picky = 0
mergeList = []
while (L1[index1][1] > L2[index2][0]):
if (L1[index1][0] < L2[index2][0]):
pickx = L2[index2][0]
else:
pickx = L1[index1][0]
if (L1[index1][1] < L2[index2][1]):
picky = L1[index1][1]
else:
picky = L2[index2][1]
mergeList.append([pickx,picky])
index2 = index2+1
if (index2 == len2):
break

if (L2[index2][0] < L1[index1][1]):
continue
else:
index1 = index1 + 1
if (index1 == len1-1):
exit

return mergeList

L1 = [[0,4], [7,12]]
L2 = [[1,3], [5,8], [9,11]]
print mergeLists(L1, L2)

``````

• What position did you interview for and is this for new grads?

• Let A = {a`1`, a`2`, a`3`, ..., a`n-1`, a`n`} where a`n` is a pair of (`x`, `y`)
and B = {b`1`, b`2`, b`3`, ..., b`m-1`, b`m`} where b`m` is is pair of (`x`, `y`)

Now A`^`B = {a1`^`B, a2`^`B, ...., an-1`^`B, an`^`B}
= {a1`^`b1...a1`^`bm, a2`^`b1...a2`^`bm, .... an-1`^`b1...an-1`^`bm, an`^`b1...an`^`bm}

where `^` is an operator computed as the following code

`List L`
`for i = 1 to n`
`for j = 1 to m`
`if(a[i].x <= b[j].x && a[i].y >= b[j].y )`
`L.put(b[j]);`
`else if(a[i].x >= b[j].x && a[i].y <= b[j].y )`
`L.put(a[i]);`
`else`
`skip_to_the_next_level`
`end for j`
`end for i`

`return L`

• Here is my python implementation... just structured it for easy understanding.. Idea is to first see if B's start falls within A's end.. if not then go the next list of A.. if Ture, then B's start lies within A. Now fix the end of the B.. if it is within A's end then just insert it into the result other wise B's end overlays current A.. so reduce the start of the B.

`````` class overlapList:
def __init__(self, A, B):
self.A = A
self.B = B
def printOverlapList(self):
i = 0
j = 0
res = []
if(not len(A) or not len(B)):
return res

A_start = A[0][0]
A_end = A[0][1]
B_start = B[0][0]
B_end = B[0][1]
while(i != len(A) and j != len(B)) :
# Current interval of B is out of range of current interval of A
# Go to the next A interval
if(B_start > A_end):
i = i + 1
if(i < len(A)) :
A_start = A[i][0]
A_end = A[i][1]
continue

# There is an overlap .. just check if B starts before A or After A.
if(B_start < A_start):
B_start = A_start
# We have fixed start of the overlap, let's fix end of the overlap
# if B end is withing A end insert into the result and go to next B
if(B_end <= A_end):
res.append([B_start,B_end])
j = j + 1
A_start = B_end + 1
if(j < len(B)) :
B_start = B[j][0]
B_end = B[j][1]
else:
# B's end extends beyon A end, fix B start and go to the next A
res.append([B_start,A_end])
B_start = A_end + 1
i = i + 1
if(i < len(A)):
A_start = A[i][0]
A_end = A[i][1]
return res

A = [[0,4],[7,12]]
B = [[1,3],[5,8],[9,11]]

l = overlapList(A, B)
res = l.printOverlapList()
for a in res:
print ("[ %d %d]"%(a[0],a[1])),
``````

• We can convert interval list to a list of state change happen at different timestamp, for example, list A = [1,4], [5,8] means enter A at 1, and exit A at 4, then enter A again at 5 and exit A at 8. Similarly list B = [0, 3], [6, 10] means enter B at 0, exit B at 3, enter B at 6, exit B at 10. we can represent these enter/exit events by
(1, +A), (4, -A), (5, +A), (8, -A)
(0, +B), (3, -B), (6, +B), (10, -B)

Then to find common intervals, we can merge two events and sort them by time, e.g.
(0, +B), (1, +A), (3, -B), (4, -A), (5, +A), (6, +B), (8, -A), (10, -B)

Then you can iterate this list and check at every -A or -B point to see if both #A > 0 and #B > 0 at the moment, if yes, that interval is a common interval. So when we check (3, -B) we found both #A > 0 and #B > 0, so [1,3] is a common interval. Then check (8, -A), found [6,8] is common interval.

This method is working on both overlap and non-overlap intervals.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.