# Merge two interval lists

• Given A and B two interval lists, A has no overlap inside A and B has no overlap inside B. Write the function to merge two interval lists, output the result with no overlap. Ask for a very efficient solution

A naive method can combine the two list, and sort and apply merge interval in the leetcode, but is not efficient enough.

For example,
A: [1,5], [10,14], [16,18]
B: [2,6], [8,10], [11,20]

output [1,6], [8, 20]

• are intervals sorted by start time or not?

• ``````AList = [[1,5], [10,14], [16,18]]
BList = [[2,6], [8,10], [11,20]]
AList = [[1, 6], [7, 9]]
BList = [[2, 8], [9,11]]

def intersect(aWindow, bWindow):
[aStart, aEnd] = aWindow
[bStart, bEnd] = bWindow
mergeWindow = []

# aWindow start from bWindow
if bStart <= aStart <= bEnd:
mergeWindow.append(bStart)
elif aStart <= bStart <= aEnd:
mergeWindow.append(aStart)

if mergeWindow:
mergeWindow.append(max([aWindow[1], bWindow[1]]))

return mergeWindow

def self_interval_merge(iList):
ilistlen = len(iList)
if ilistlen <= 1:
return iList
else:
for i in range(ilistlen):
a = iList[i]
b = iList[i + 1]
d = intersect(iList[i], iList[i + 1])
if d:
iList.remove(a)
iList.remove(b)
iList.append(d)
break

if ilistlen == len(iList):
return iList

return self_interval_merge(iList)

def rec_fun(AList, BList):
flag = True
aLen = len(AList)
bLen = len(BList)

for a in AList:
if not flag:
break
for b in BList:
d = intersect(a, b)
if d:
AList.remove(a)
BList.remove(b)

if d[0] == a[0]:
AList = [d] + AList
elif d[0] == b[0]:
BList = [d] + BList

break

if aLen == len(AList) and bLen == len(BList):
return self_interval_merge(AList + BList)

return rec_fun(AList, BList)

``````

• @nshah
It won't work for inputs:

``````a1 = [[1, 6], [7, 9]]
b1 = [[2, 8]]
print(rec_fun(a1, b1))
# Results in [[1, 8], [7, 9]]
# answer should be [[1, 9]]
``````

You are changing the lists as you are iterating through them. Not a good idea.

• @elmirap @evani1208 If the lists are sorted by start time, you just `popleft()` the one having less start time and merge with the current vector of intervals.

• @kmad1729 I ignored/forgot about the case where they may wind up overlapping each other in the same list. I have updated my response.

• Two pointer solution:

``````def union_intvl(a, b):
result = []
if a[0] <= b[0] <= a[1]:
result = [a[0], max(a[1], b[1])]
elif b[0] <= a[0] <= b[1]:
result = [b[0], max(a[1], b[1])]
return result

def merge_intvl_lists(A, B):
i = 0
j = 0
curr_merged_list = []
result = []
while i < len(A) or j < len(B):
if len(curr_merged_list) == 0:
if i < len(A):
if j < len(B):
curr_merged_list = min(A[i], B[j])
if curr_merged_list == A[i]:
i += 1
else:
j += 1
else:
curr_merged_list = A[i]
i += 1
else:
curr_merged_list = B[j]
j += 1

if i < len(A):
r1 = union_intvl(curr_merged_list, A[i])
else:
r1 = []
if len(r1) != 0:
curr_merged_list = r1
i += 1

if j < len(B):
r2 = union_intvl(curr_merged_list, B[j])
else:
r2 = []

if len(r2) != 0:
curr_merged_list = r2
j += 1
if len(r1) == 0 and len(r2) == 0:
result.append(curr_merged_list)
curr_merged_list = []

if len(curr_merged_list) != 0:
result.append(curr_merged_list)

return result
``````

• @evanl1208 what is the complexity that is requested ? are the two lists sorted ? if each list is sorted then I would expect O(M + N) to be the expected runtime.

• @galster assume that O(m+n), yes arrays are sorted in ascending way without overlaps between intervals in the arrays

• @evanl1208

``````    public static List<Interval> merge(List<List<Interval>> lsts)
{
List<Interval> result = new List<Interval>();
Dictionary<int, int> dict = new Dictionary<int, int>();
for (int i = 0; i < lsts.Count; i++){
dict[i] = 0;
}
Interval curr = lsts[0][0];
dict[0] = 1;
bool flag = false;
while (dict.Count > 0)
{
flag = false;
for (int i = 0; i < lsts.Count; i++)
{
if (dict.ContainsKey(i) && dict[i] < lsts[i].Count)
{

Interval it = lsts[i][dict[i]];
if (curr == null)
{
curr = it; continue;
}
if((it.start>=curr.start&&it.start<=curr.end)||
(curr.start >= it.start && curr.start <= it.end))
{
flag = true;
curr.start = Math.Min(curr.start, it.start);
curr.end = Math.Max(curr.end, it.end);
dict[i]++;
}
}
else
{
dict.Remove(i);
}
}
if (flag == false)
{
curr = null;
}
}
return result;

}``````

• we could solve this in linear time.

psuedo code:

``````while we are not done do
pick smaller Pair P from A & B
if C is not empty
try to merge P with C.last_element
if cannot merge then add P
else remove C.last_element and add P
if C is empty just add P

move through the other list (if you picked P from A move through B, if you picked P from B move through A)
for each Pair P try to merge with C.last_element
if can merge then remove C.last_element and add P
else break and go the beginning of the while loop
``````

• Similar to merging two sorted lists

``````def mergeIntervals(int1, int2):
if not int1 or not int2:
return int1 or int2
ret = []
i = 0
j = 0
if int1[0][0] < int2[0][0]:
curr = int1[0]
i = 1
else:
curr = int2[0]
j = 1

while i < len(int1) or j < len(int2):
if j == len(int2) or int1[i][0] < int2[j][0]:
nxt = int1[i]
i += 1
else:
nxt = int2[j]
j += 1
if curr[1] < nxt[0]:
ret.append(curr)
curr = nxt
else:
curr[1] = max(curr[1], nxt[1])
ret.append(curr)

return ret
``````

• Full working Java example, based on logic of merging 2 sorted list.

...
import java.util.*;

class MergeIntervals {

``````static class Interval {
int start;
int end;
Interval(int a, int b) {
this.start = a;
this.end = b;
}

public boolean overlaps(Interval b) {
if((this.start <= b.end && this.end >= b.start) ||
(b.start <= this.end && b.end >= this.start))
return true;

return false;
}
}

static List<Interval> mergeIntervalFinal(List<Interval> list1, List<Interval> list2) {

List<Interval> result = new ArrayList<Interval>();
int list1Len = list1.size();
int list2Len = list2.size();
int i = 0;
int j = 0;

while(i < list1Len && j < list2Len) {
Interval i1 = list1.get(i);
Interval i2 = list2.get(j);
int resSize = result.size();
if(resSize > 0) {
Interval temp = result.get(resSize - 1);
if(temp.overlaps(i1) || temp.overlaps(i2)) {
Interval interval = null;
if(temp.overlaps(i1)) {
interval = mergeUtil(temp, i1);
i++;
} else {
interval = mergeUtil(temp, i2);
j++;
}
result.remove(resSize - 1);
continue;
}
}
if(i1.overlaps(i2)) {
Interval newInterval = mergeUtil(i1, i2);
i++;
j++;
} else if(i1.start > i2.end) {
j++;
} else {
i++;

}
}
if(j < list2Len) {
list1 = list2;
i = j;
}
while(i < list1.size()) {
Interval i1 = list1.get(i);
Interval temp = result.get(result.size() - 1);
if(temp.overlaps(i1)) {
i1 = mergeUtil(temp, i1);
result.remove(result.size() - 1);
}
i++;
}
return result;

}

static Interval mergeUtil (Interval i1, Interval i2) {
Interval newInterval = new Interval(Math.min(i1.start, i2.start), Math.max(i1.end, i2.end));
return newInterval;
}

public static void main(String a[]) {

List<Interval> list = new ArrayList<Interval>();
List<Interval> list2 = new ArrayList<Interval>();
/*Interval i1 = new Interval(1,5);
i1 = new Interval(10,14);
i1 = new Interval(16,18);
i1 = new Interval(20,22);
i1 = new Interval(25,28);

i1 = new Interval(2,6);
i1 = new Interval(8,10);
i1 = new Interval(11,20);
i1 = new Interval(23,25);
*/
//List<Interval> result = mergeInterval(list, list2);
//printIntervals(result);
/*Interval i1 = new Interval(1,5);

i1 = new Interval(1,5);
i1 = new Interval(10,14);
i1 = new Interval(16,18);

i1 = new Interval(2,6);
i1 = new Interval(8,10);
i1 = new Interval(11,20);
*/
Interval i1 = new Interval(3,11);
i1 = new Interval(17,25);
i1 = new Interval(58,73);

i1 = new Interval(6,18);
i1 = new Interval(40,47);

List<Interval> result = mergeIntervalFinal(list, list2);
printIntervals(result);

}

static void printIntervals(List<Interval> result){
for(Interval i: result) {
System.out.println(i.start + "-" + i.end);
}
}
``````

}
...

• ``````public static List<Interval> merge(List<Interval> a, List<Interval> b) {
if(a == null && b == null) {
return null;
}

if(a == null) {
return b;
}

if(b == null) {
return a;
}

List<Interval> ret = new ArrayList<>();

int i = 0, j = 0;
// pick the smallest start time interval
Interval prev = a.get(0).start < b.get(0).start ? a.get(0):b.get(0);
while(i < a.size() && j < b.size()) {
Interval p = a.get(i);
Interval q = b.get(j);

// if p < q
if(p.compareTo(q) < 0) {
// check if p starts after prev, then there is no overlap
if(p.start >= prev.end) {
prev = p;
} else { // there is overlap, then just merge the end
prev.end = Math.max(prev.end, p.end);
i++;
}
} else { // same here
if(q.start >= prev.end) {
prev = q;
} else {
prev.end = Math.max(prev.end, q.end);
j++;
}
}
}

// Repeat if a is not yet exhaused
while(i < a.size()) {
Interval p = a.get(i);
if(p.start >= prev.end) {
prev = p;
} else {
prev.end = Math.max(prev.end, p.end);
i++;
}
}

// Repeat if b is not yet exhaused
while(j < b.size()) {
Interval q = b.get(j);
if(q.start >= prev.end) {
prev = q;
} else {
prev.end = Math.max(prev.end, q.end);
j++;
}
}

// Add the prev interval again
return ret;
}

private static class Interval implements Comparable<Interval>{
int start;
int end;

public Interval(int start, int end) {
this.start = start;
this.end = end;
}

@Override
public int compareTo(Interval o) {
return this.start - o.start;
}

@Override
public String toString() {
return "[" + start + ", " + end + "]";
}
}
``````

• Working Java solution: use two pointers

``````import java.util.*;

class Interval {
int start;
int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}

class myComparator implements Comparator<Interval> {
@Override
public int compare(Interval i1, Interval i2) {
if (i1.start == i2.start) {
return 0;
} else {
return i1.start < i2.start? -1: 1;
}
}
}

public class IntervalMerge {
public List<Interval> mergeList(List<Interval> l1, List<Interval> l2) {
if (l1 == null || l1.size()  == 0) {
return l2;
} else if (l2 == null || l2.size() == 0) {
return l1;
}

Collections.sort(l1, new myComparator());
Collections.sort(l2, new myComparator());

List<Interval> result = new ArrayList<>();
int ix1 = 0;
int ix2 = 0;
// Get the first interval
Interval prev = null;
if (l1.get(0).start < l2.get(0).start) {
prev = l1.get(0);
ix1 ++;
} else {
prev = l2.get(0);
ix2 ++;
}
// Move two pointers to merge lists
while (ix1 < l1.size() || ix2 < l2.size()) {
if (ix2 == l2.size() || (ix1 < l1.size() && l1.get(ix1).start < l2.get(ix2).start)) {
// merge prev with ix1
if (prev.end < l1.get(ix1).start) {
prev = l1.get(ix1);
} else {
prev.end = Math.max(prev.end, l1.get(ix1).end);
}
ix1 ++;
} else {
// merge prev with ix2
if (prev.end < l2.get(ix2).start) {
prev = l2.get(ix2);
} else {
prev.end = Math.max(prev.end, l2.get(ix2).end);
}
ix2 ++;
}
}
return result;
}

public static void main(String[] args) {
IntervalMerge myObj = new IntervalMerge();

List<Interval> l1 = new ArrayList<>();
List<Interval> l2 = new ArrayList<>();

List<Interval> result = myObj.mergeList(l1, l2);
for (Interval i1: result) {
System.out.println(i1.start + ", " + i1.end);
}
}

}

``````

• // Map the intervals into Cartesian axis. Set y = 1 for start time and y = -1 for end time.
vector<pair<int, int>> mergeIntervals(vector<pair<int, int>> A, vector<pair<int, int>> B)
{
map<int, int> mp;

``````for (auto a : A)
{
mp[a.first] = 1;
mp[a.second] = -1;
}

for (auto b : B)
{
mp[b.first]++;
mp[b.second]--;
}

int cnt = 0;
int first = 0;
vector<pair<int, int>> res;
for (auto m : mp)
{
if (cnt == 0 && m.second > 0)
{
first = m.first;
}

cnt += m.second;

if (cnt == 0 && m.second < 0)
{
res.push_back(make_pair(first, m.first));
}
}

return res;
``````

}

• ``````def solve(A,B):
A.extend(B)
a = sorted(A, key=lambda x: x[0])

prev=None
start = []
end = []

for x, y in a:
if not prev:
prev = (x, y)
start.append(x)
end.append(y)
continue
if prev[0] < x < prev[1]:
if y > prev[1]:
end[-1] = y
res+=1
else:
start.append(x)
end.append(y)
prev = (start[-1], end[-1])
return zip(start,end)
print solve([[1,5], [10,14], [16,18]],[[2,6], [8,10], [11,20]])

``````

• `````` public static void mergeLists(List<Interval> listA, List<Interval> listB) {

int a = 0;
int b = 0;

List<Interval> listC = new ArrayList<>();

while (a < listA.size() && b < listB.size()) {
Interval intervalA = listA.get(a);
Interval intervalB = listB.get(b);
Interval current =null;
if(listC.size() > 0) {
current = listC.get(listC.size() - 1);
}
Interval merged = null;
if(isOverlap(intervalA, intervalB)){
merged = merge(intervalA, intervalB);
if(current != null && isOverlap(current, merged)) {
merged = merge(current, merged);
listC.remove(listC.size()-1);
}
}
if(merged != null) {
} else {
if(intervalA.start < intervalB.start) {
} else {
}
}

if(intervalA.length() < intervalB.length()) {
a++;
} else if(intervalB.length() < intervalA.length()) {
b++;
} else {
a++;
b++;
}
}
if(a < listA.size()) {
while (a < listA.size()) {
if(isOverlap(listC.get(listC.size()-1), listA.get(a))) {
Interval merged = merge(listC.get(listC.size()-1), listA.get(a));
listC.remove(listC.get(listC.size()-1));
}
a++;
}
}

if(b < listB.size()) {
while (b < listB.size()) {
if(isOverlap(listC.get(listC.size() - 1), listB.get(b))) {
Interval merged = merge(listC.get(listC.size()-1), listB.get(b));
listC.remove(listC.get(listC.size()-1));
}
b++;
}
}

System.out.println(listC);

}
``````

• @agave I Imagine though that at the end(once all merges are done). You would have to make another pass through the list to ensure there is no overlap

• Here is my c++ code using two pointer:

`````` vector<pair<int, int>> mergeNonOverlappingIntervals(vector<pair<int, int>>& a, vector<pair<int, int>>& b) {
int s = INT_MIN, e = INT_MIN, i = 0, j = 0;
vector<pair<int,int>> res;
while (i < a.size() || j < b.size()) {
pair<int, int> cur;
if (i >= a.size()) cur = b[j++];
else if (j >= b.size()) cur = a[i++];
else cur = a[i].first < b[j].first ? a[i++] : b[j++];
if (cur.first > e) {
if (e > INT_MIN)
res.emplace_back(s, e);
s = cur.first;
e = cur.second;
}
else {
e = max(cur.second, e);
}
}
if (e > INT_MIN) res.emplace_back(s, e);
return res;

}
``````

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