Merge two interval lists


  • 3
    E

    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]


  • 2

    are intervals sorted by start time or not?


  • 0
    N
    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)
    
                    
    print('Answer : ', rec_fun(AList, BList))                    
    

  • 0
    K

    @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.


  • 0

    @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.


  • 0
    N

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


  • 0
    K

    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
    

  • 0
    G

    @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.


  • 0

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


  • 0
    S

    @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)
                {
                    result.Add(curr);
                    curr = null;
                }
            }
            return result;
            
            
        }

  • 0

    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
    

  • 2
    W

    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
    

  • 1
    J

    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);
    				result.add(interval);
    				continue;
    			}
    		}
    		if(i1.overlaps(i2)) {
    			Interval newInterval = mergeUtil(i1, i2);
    			result.add(newInterval);
    			i++;
    			j++;
    		} else if(i1.start > i2.end) {
    			result.add(i2);
    			j++;
    		} else {
    			result.add(i1);
    			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);
    		} 
    		result.add(i1);
    		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);
    	list.add(i1);
    	i1 = new Interval(10,14);
    	list.add(i1);
    	i1 = new Interval(16,18);
    	list.add(i1);
    	i1 = new Interval(20,22);
    	list.add(i1);
    	i1 = new Interval(25,28);
    	list.add(i1);
    	
    	i1 = new Interval(2,6);
    	list2.add(i1);
    	i1 = new Interval(8,10);
    	list2.add(i1);
    	i1 = new Interval(11,20);
    	list2.add(i1);
    	i1 = new Interval(23,25);
    	list2.add(i1);
    	 */ 
    	//List<Interval> result = mergeInterval(list, list2);
    	//printIntervals(result);
    	/*Interval i1 = new Interval(1,5);
    	
    	i1 = new Interval(1,5);
    	list.add(i1);
    	i1 = new Interval(10,14);
    	list.add(i1);
    	i1 = new Interval(16,18);
    	list.add(i1);
    	
    	i1 = new Interval(2,6);
    	list2.add(i1);
    	i1 = new Interval(8,10);
    	list2.add(i1);
    	i1 = new Interval(11,20);
    	list2.add(i1);
    	*/
    	Interval i1 = new Interval(3,11);
    	list.add(i1);
    	i1 = new Interval(17,25);
    	list.add(i1);
    	i1 = new Interval(58,73);
    	list.add(i1);
    	
    	i1 = new Interval(6,18);
    	list2.add(i1);
    	i1 = new Interval(40,47);
    	list2.add(i1);
    	
    	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);
    	}
    }
    

    }
    ...


  • 0
    M
    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) {
    					ret.add(prev);
    					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) {
    					ret.add(prev);
    					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) {
    				ret.add(prev);
    				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) {
    				ret.add(prev);
    				prev = q;
    			} else {
    				prev.end = Math.max(prev.end, q.end);
    				j++;
    			}
    		}
    		
    		// Add the prev interval again
    		ret.add(prev);
    		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 + "]";
    		}
    	}
    

  • 5
    J

    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) {
    					result.add(prev);
    					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) {
    					result.add(prev);
    					prev = l2.get(ix2);
    				} else {
    					prev.end = Math.max(prev.end, l2.get(ix2).end);
    				}
    				ix2 ++;
    			}
    		}		
    		result.add(prev);
    		return result;
    	}
    	
    	public static void main(String[] args) {
    		IntervalMerge myObj = new IntervalMerge();
    		
    		List<Interval> l1 = new ArrayList<>();
    		l1.add(new Interval(1, 5));
    		l1.add(new Interval(10, 14));
    		l1.add(new Interval(16, 18));
    		l1.add(new Interval(20, 24));
    		l1.add(new Interval(30, 38));
    		List<Interval> l2 = new ArrayList<>();
    		l2.add(new Interval(2, 6));
    		l2.add(new Interval(8, 10));
    		l2.add(new Interval(11, 20));
    		
    		List<Interval> result = myObj.mergeList(l1, l2);
    		for (Interval i1: result) {
    			System.out.println(i1.start + ", " + i1.end);
    		}
    	}
    	
    }
    
    
    

  • 0
    D

    // 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;
    

    }


  • 1
    S
    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]])
    
    
    

  • 1
    S
     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) {
                listC.add(merged);
             } else {
                if(intervalA.start < intervalB.start) {
                   listC.add(intervalA);
                   listC.add(intervalB);
                } else {
                   listC.add(intervalB);
                   listC.add(intervalA);
                }
             }
    
    
             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));
                  listC.add(merged);
               }
               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));
                   listC.add(merged);
                }
                b++;
             }
          }
    
          System.out.println(listC);
    
       }
    

  • 0
    P

    @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


  • 1
    A

    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;
    
        }
    

Log in to reply
 

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