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


  • 0
    F
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    /*handle special case when original intervals is empty*/
        if(intervals.size() == 0){
            intervals.add(newInterval);
            return intervals;
        }
    /*determine the start and end of the new interval we want 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;
        }
    /*create a new list and do the insertion*/
        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.