LintCode 839 - Merge Two Sorted Interval Lists

https://www.lintcode.com/en/old/problem/merge-two-sorted-interval-lists/

Merge two sorted (ascending) lists of interval and return it as a new sorted list. The new sorted list should be made by splicing together the intervals of the two lists and sorted in ascending order.

 Notice

• The intervals in the given list do not overlap.
• The intervals in different lists may overlap.

Example

Given list1 = [(1,2),(3,4)] and list2 = [(2,3),(5,6)], return [(1,4),(5,6)]

https://www.jiuzhang.com/solution/merge-two-sorted-interval-lists/

  public List<Interval> mergeTwoInterval(List<Interval> list1, List<Interval> list2) {

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

    if (list1 == null || list2 == null) {

      return results;

    }

    Interval last = null, curt = null;

    int i = 0, j = 0;

    while (i < list1.size() && j < list2.size()) {

      if (list1.get(i).start < list2.get(j).start) {

        curt = list1.get(i);

        i++;

      } else {

        curt = list2.get(j);

        j++;

      }

      last = merge(results, last, curt);

    }

    while (i < list1.size()) {

      last = merge(results, last, list1.get(i));

      i++;

    }

    while (j < list2.size()) {

      last = merge(results, last, list2.get(j));

      j++;

    }

    if (last != null) {

      results.add(last);

    }

    return results;

  }

  private Interval merge(List<Interval> results, Interval last, Interval curt) {

    if (last == null) {

      return curt;

    }

    if (curt.start > last.end) {

      results.add(last);

      return curt;

    }

    last.end = Math.max(last.end, curt.end);

    return last;

  }

https://blog.csdn.net/roufoo/article/details/82703034
    vector<Interval> mergeTwoInterval(vector<Interval> &list1, vector<Interval> &list2) {
        if (list1.size() == 0) return list2;
        else if (list2.size() == 0) return list1;

        vector<Interval> result;

        int p1 = 0, p2 = 0;
        Interval itv;
        if (list1[p1].start < list2[p2].start)
            itv = Interval(list1[p1].start, list1[p1].end);
        else
            itv = Interval(list2[p2].start, list2[p2].end);

        while ((p1 < list1.size()) || (p2 < list2.size())) {

            if (p1 < list1.size() && isOverlapping(list1[p1], itv)) {
                itv = merging(list1[p1], itv);
                p1++;
            } else if (p2 < list2.size() && isOverlapping(list2[p2], itv)) {
                itv = merging(list2[p2], itv);
                p2++;
            } else {
                result.push_back(itv);
                if (p1 < list1.size() && p2 < list2.size()) {
                    if (list1[p1].start < list2[p2].start)
                        itv = Interval(list1[p1].start, list1[p1].end);
                    else
                        itv = Interval(list2[p2].start, list2[p2].end);
                } else if (p1 < list1.size())
                    itv = Interval(list1[p1]);
                else
                    itv = Interval(list2[p2]);
            }
        }

        result.push_back(itv);

        return result;
    }

private:
    bool isOverlapping(Interval const & itv1, Interval const & itv2) {
        if ((itv1.end >= itv2.start) && (itv1.end <= itv2.end))  return true;
        if ((itv2.end >= itv1.start) && (itv2.end <= itv1.end))  return true;
        return false;
    }

    Interval merging(Interval const & itv1, Interval const & itv2) {
        return Interval(min(itv1.start, itv2.start), max(itv1.end, itv2.end));
    }
https://github.com/jiadaizhao/LintCode/blob/master/0839-Merge%20Two%20Sorted%20Interval%20Lists/0839-Merge%20Two%20Sorted%20Interval%20Lists.cpp
    vector<Interval> mergeTwoInterval(vector<Interval> &list1, vector<Interval> &list2) {
        // write your code here
        vector<Interval> result;
        int i = 0, j = 0;
        while (i < list1.size() || j < list2.size()) {
            if (j == list2.size() || (i < list1.size() && list1[i].start <= list2[j].start)) {
                if (result.size() && list1[i].start <= result.back().end) {
                    result.back().end = max(result.back().end, list1[i].end);
                }
                else {
                    result.push_back(list1[i]);
                }
                ++i;
            }
            else {
                if (result.size() && list2[j].start <= result.back().end) {
                    result.back().end = max(result.back().end, list2[j].end);
                }
                else {
                    result.push_back(list2[j]);
                }
                ++j;
            }
        }
        return result;

    }

https://github.com/mission-peace/interview/blob/master/src/com/interview/misc/AddingTwoSetOfIntervals.java
    public List<Pair> combineInterval(Pair[] arr1, Pair[] arr2){
        Arrays.sort(arr1);
        Arrays.sort(arr2);
     
        List<Pair> result = new ArrayList<Pair>();
        int i=0;
        int j=0;
        Pair current = new Pair(Integer.MIN_VALUE,Integer.MIN_VALUE+1);
        while(i < arr1.length && j < arr2.length){
            if(arr1[i].low <= arr2[j].low){
                if(arr1[i].low <= current.high){
                    current.high = Math.max(arr1[i].high,current.high);
                }else{
                    current = arr1[i];
                    result.add(current);
                }
                i++;
            }
            else{
                if(arr2[j].low <= current.high){
                    current.high = Math.max(arr2[j].high,current.high);
                }else{
                    current = arr2[j];
                    result.add(current);
                }
                j++;
            }
        }
        while(i < arr1.length){
            if(arr1[i].low <= current.high){
                current.high = Math.max(current.high,arr1[i].high);
            }else{
                current = arr1[i];
                result.add(current);
            }
            i++;
        }
        while(j < arr2.length){
            if(arr2[j].low <= current.high){
                current.high = Math.max(current.high, arr2[j].high);
            }else{
                current = arr2[j];
                result.add(current);
            }
            j++;
        }
     
        return result;
    }
X. https://www.jianshu.com/p/4ec67ce48833

  public List<Interval> mergeTwoInterval(List<Interval> list1, List<Interval> list2) {

    list1.addAll(list2);

    Collections.sort(list1, new Comparator<Interval>() {

      @Override

      public int compare(Interval o1, Interval o2) {

        return o1.start - o2.start;

      }

    });

    for (int i = 0; i < list1.size() - 1; i++) {

      Interval first = list1.get(i);

      Interval next = list1.get(i + 1);

      if (first.end < next.start) {

        continue;

      } else {

        first.end = Math.max(next.end, first.end);

        list1.remove(i + 1);

        i--;

      }

    }

    return list1;

  }