Insert and Merge Interval

InsertAndMergeInterval.java

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
         List<Interval> merged = new ArrayList<Interval>();
         int n = intervals.size();
       
         int j = 0;
         while (j < n && newInterval.start > intervals.get(j).end ){
             merged.add(intervals.get(j));
             j++;
         }
 
         Interval lastInterval = newInterval;
         int i = j;
         while ( i < n && isOverlap(intervals.get(i), newInterval)){
             Interval temp = intervals.get(i);
             lastInterval.start = Math.min(lastInterval.start, temp.start);
             lastInterval.end = Math.max(lastInterval.end, temp.end);
             i++;
         }
         merged.add(lastInterval);
             
         while (i < n){
             merged.add(intervals.get(i));
             i++;
         }
        return merged;
            
    }
    
    public boolean isOverlap(Interval x, Interval y){
      if (x.start <= y.end){
        return true;
      }
      return false;
   }    
    
}


//Testing:



import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Comparator;
import java.util.Formatter;

public class TestRanges
{
  public static void main(String[] args)
  {
    List<Range> list = new ArrayList<Range>();
    list.add(new Range(1, 5));
    list.add(new Range(17, 22));
    list.add(new Range(9, 13));
    
    Range newRange = new Range(4, 10);
             
    List<Range> mergedList = mergeNewRange(list, newRange);
    
    for (int i = 0; i < mergedList.size(); i++){
      Range temp = mergedList.get(i);
      
      System.out.println(String.format(" %-3d, %-3d ", temp.start, temp.end));
      
    }
  }
  
  public static List<Range> mergeNewRange(List<Range> list, Range newRange){
   List<Range> merged = new ArrayList<Range>();
   int n = list.size();
    
    Collections.sort(list, new Comparator<Range>(){
      @Override
      public int compare(Range r1, Range r2){
         return (r1.start - r2.start); 
      }
    });
    
    int i = 0;
    while (i < n && !isOverlap(list.get(i), newRange)){
    	merged.add(list.get(i));
        i++;       
    }
    
    //get merged intervals
    int j = i;
    Range temp = newRange;
    while (j < n && isOverlap(list.get(j), newRange)){
      newRange.start = Math.min(list.get(j).start, newRange.start);
      newRange.end = Math.max(list.get(j).end, newRange.end);
      j++;
    }
    merged.add(newRange);
    
    while (j < n){
      merged.add(list.get(j));
      j++;
    }
           
    return merged;
  }
  
  public static boolean isOverlap(Range r1, Range r2){
    if (r1.start < r2.end) return true;
    return false;
  }
}

public class Range
{
  public int start;
  public int end;
  public Range(int b, int e)
  {
    this.start = b;
    this.end = e;
  }
  
}