[Sort][Interval] Insert Interval

1. Example

s= [ [1,3], [6,9] ]
insert [2,5]
=>s= [  [1,5], [6,9]  ]

s= [  [1,2], [3,5], [6,7], [8,10], [12,16]  ]
insert [4,9]
=> s= [ [1,2], [3,10], [12,16]  ]

[4,9] overlaps [3,5], [6,7], [8,10]



2. Implementation
Q1: can we reuse merge interval?
A1: insert interval first and do the merge
Q1: how to insert ?
A1: check start if start equal , check end
// Add those less than newInterval.start

 int i = 0; while ( i < intervals.size() && intervals.get(i).end < newInterval.start) { res.add(intervals.get(i)); i++; } 

// Add newInterval

 if ( i < interval.size()) newInterval.start = Math.min(newInterval.start, intervals.get(i).start); res.add(newInterval); 

// Add the rest less than interval.end 

while(i < intervals.size() && intervals.get(i).start <= newInterval.end) { newInterval.end = Math.max(newInterval.end, intervals.get(i).end); i++; }

// Time:O(n), Space:O(n) List
public List insert(List intervals, Interval newInterval)
{
          
       

       
       
        List res = new ArrayList();




        // validate the input
        if ( intervals == null || intervals.size() ==0 )
        {
               res.add(newInterval);
               return res;
        }     
        if (newInterval == null )
        {
               return intervals;
        }





        // Insert newInterval
        List resTemp = new ArrayList();
        resTemp.add(newInterval);
        for (int i =0 ; i < intervals.size(); i++ )
        {
              if (resTemp.get(resTemp.size()-1).start > intervals.get(i).start)
              {
                    int pos=resTemp.size()-1;
                    Interval temp = resTemp.get(pos);
                    resTemp.set(pos, intervals.get(i));
                    resTemp.add(temp);
              }        
              else 
                 resTemp.add(intervals.get(i));
        }   





        // Merge Interval
        res.add(resTemp.get(0));
        for (int i =1; i < resTemp.size(); i++)
        {
              if(   res.get(res.size()-1).end >= resTemp.get(i).start  )  
                    res.get(res.size()-1).end = Math.max( res.get(res.size()-1).end, resTemp.get(i).end  );
              else
                    res.add(resTemp.get(i));
        }



       
        return res;       
       
       


}

public List insert (List intervals, Interval newInterval)
{




      List res = new ArrayList();




      if (intervals.size() == 0)
      {
           res.add(newInterval);
           return;
      }




      // Add those less than newInterval.start
      int i = 0;
      while ( i < intervals.size() && intervals.get(i).end < newInterval.start)
      {
         res.add(intervals.get(i));
         i++;
      }





      // Add newInterval
      if ( i < interval.size())
           newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
      res.add(newInterval);





      // Add the rest less than interval.end
      while(i < intervals.size() && intervals.get(i).start <= newInterval.end)
      {
           newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
           i++;
      }




      // Add the rest 
      while ( i < intervals.size())
      {
             res.add(intervals.get(i));
             i++;
      }
 



      return res;
 
           
}

3. Similar ones
Merge Interval
Sort Color
Sort List