Merge two interval lists


  • 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
    

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

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