# 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;
  }

} ```

results matching ""

    No results matching ""