Merge Sorted Array, Merge Intervals, Insert Interval

Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Two Pointer Solution:

Unlike merge sort, we need to merge these two arrays in place. So start from the end (A[m+n-1]), we compare each pointer. Until one of the pointers reached 0, copy the rest of B to A.

public void merge(int A[], int m, int B[], int n) {
        int cur=m+n;
        while(m>0 && n>0){
             if(A[m-1]<B[n-1]){A[--cur]=B[--n];}
             else {A[--cur]=A[--m];}
        }
        while(n>0){A[--cur]=B[--n];}
    }

---

Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Correct Solution

At first sort the Intervals, then I thought of three basic cases:

cur.end > next.end (&& cur.end > next.start)

cur.end < next.end && cur.end > next.start

cur.end < next.end && cur.end < next.start

we can leave the third case alone, and only the first two cases need to be merged: if(cur.end > next.start) we set cur.end to the max out of two ends.

  
  public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
  //sort according to start using inline comparator
  Collections.sort(intervals, new Comparator<Interval>(){
    public int compare(Interval a, Interval b) {
      return a.start-b.start;
    }
  });
  //compare and add to result
  ArrayList<Interval> res=new ArrayList<Interval>();
  for(int i=0;i<intervals.size();i++){
    Interval cur=intervals.get(i);
    //imagine cur to eat all overlapped intervals
    while(i<intervals.size()-1 && cur.end>=intervals.get(i+1).start){
      cur.end=Math.max(cur.end, intervals.get(i+1).end);
      i++;
    }
    res.add(cur);
  }
  return res;
}

---

Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Solution(while loop)

Still three cases:

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        int i=0; Interval cur=null;
        if(intervals.size()==0) {intervals.add(newInterval); return intervals;}
        
        while(i<intervals.size()){
          cur=intervals.get(i);
          //nonoverlap, newInterval is behind current, continue
          if(cur.end<newInterval.start) {i++;continue;}
          //nonoverlap, newInterval is before current, jump out of loop
          else if(cur.start>newInterval.end) break;
          //overlap, update newInterval and remove current
          else {
            newInterval.start=Math.min(newInterval.start, cur.start);
            newInterval.end=Math.max(newInterval.end, cur.end);
            intervals.remove(i);
          }
        }
        intervals.add(i, newInterval);
         return intervals;
        }

Solution(For each loop)

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
       ArrayList<Interval> res = new ArrayList<Interval>();
//for each interval in list, add to res
       for(Interval interval: intervals){
           if(interval.end < newInterval.start){
               res.add(interval);
           }
           else if(interval.start > newInterval.end){
               res.add(newInterval);
               newInterval = interval;        
           }
           else {
               newInterval.start=Math.min(interval.start, newInterval.start);
               newInterval.end=Math.max(newInterval.end, interval.end);
           }
       }
       res.add(newInterval); 
       return res;

Solution(ListIterator)

ListIterator:

hasNext(), next(), add(), hasPrevious(), previous(),remove(), set(), nextIndex(), previousIndex()

Iterator:

hasNext(), next(), remove()

  
  public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
  Interval cur=null;
  if(intervals.size()==0) {intervals.add(newInterval); return intervals;}
  ListIterator<Interval> it=intervals.listIterator();
  while(it.hasNext()){
    cur=it.next();
    //nonoverlap, newInterval is before current, jump out of loop
    if(newInterval.end<cur.start) {it.previous();it.add(newInterval);return intervals;}
    //nonoverlap, newInterval is after current, continue
    else if(newInterval.start>cur.end) continue;
    //overlap, update newInterval, remove current
    else {
      newInterval.start=Math.min(newInterval.start, cur.start);
      newInterval.end=Math.max(newInterval.end, cur.end);
      it.remove();
    }
  }
  //if new eats the last, add new to intervals
  intervals.add(newInterval);
  return intervals;
}