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
    

  • 1
    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 + "]";
    		}
    	}
    

  • 4
    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;
    

    }


  • 0
    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]])
    
    
    

  • 0
    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


Log in to reply
 

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