Merge two interval lists


  • 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
    

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

  • 3
    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.