AC java O(n) time O(n) space solution with detailed explaination,easy to understand


  • 0
    F
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    

    /handle special case when the interval is empty/
    if(intervals.size() == 0){
    intervals.add(newInterval);
    return intervals;
    }
    /find start and end of the new interval we need to insert/
    int start = newInterval.start;
    int end = newInterval.end;
    int new_start = start;
    int new_end = end;
    for(Interval itv: intervals){
    int itv_start = itv.start;
    int itv_end = itv.end;
    if(itv_start <= start && itv_end >= start)
    new_start = itv_start;
    if(itv_start <= end && itv_end >= end)
    new_end = itv_end;
    }
    /insert the new interval to a new List/
    Interval new_interval = new Interval(new_start,new_end);
    List<Interval> res = new LinkedList<Interval>();
    res.add(new_interval);
    int pt = 0;
    for(Interval itv : intervals){
    int itv_start = itv.start;
    int itv_end = itv.end;
    if(itv_end < new_start){
    res.add(pt++,itv);
    }
    if(itv_start > new_end){
    res.add(itv);
    }
    }
    return res;
    }
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.