# 57 Insert Interval

給一個list of Interval，還有要插入此list的interval，回傳插入之後的list of interval。（該merge的要merge）

input list已經照start time排序好。

• Idea:

  • 照順序讀list，若current Interval.end < insert Interval.start，沒有重疊，且cur比insert早，直接放入答案。
  • current Interval.end > insert Interval.start，有重疊，要merge
  • current Interval.start > insert Interval.end，insert Interval比較早，且沒有重疊，把insert interval放入答案
  • 後面都依序放將去。

• Pseudocode:

  List<Interval> ans;
  for each interval in intervals,
      if newInterval.start > interval.end
          add interval to ans;
      if newInterval.end < interval.start
          add new Interval(start, end) to ans,
          add interval to ans;
      else if newInterval.start < interval.end
          record interval.start
      else if newInterval.end > interval.start
          record interval.en
  

• Code: ```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 insert(List intervals, Interval newInterval) {

     List<Interval> ans = new ArrayList<>();
    
     int s=newInterval.start, e=newInterval.end;
     int i=0;
     while(i < intervals.size() && newInterval.start > intervals.get(i).end){
          ans.add(intervals.get(i));
          i++;
     }
     while(i < intervals.size() && intervals.get(i).start <= newInterval.end){
         s = Math.min(s, intervals.get(i).start);
         e = Math.max(e, intervals.get(i).end);
         i++;
     }
     ans.add(new Interval(s,e));
     while(i < intervals.size() && intervals.get(i).start > newInterval.end){
         ans.add(intervals.get(i));
          i++;
     }
    

      return ans;
  }

} ```