Java inplace solution O(N)


  • 0
    M

    In-place solution

    class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            
            // insert newInterval with ascending order
            int ind = 0;
            while(ind < intervals.size() && intervals.get(ind).start < newInterval.start) ind++;
            intervals.add(ind, newInterval);
            
            // Merge intervals inline
            for(ListIterator<Interval> it = intervals.listIterator(), Interval cur = null; it.hasNext(); ){
                Interval i = it.next();
                if(cur == null || cur.end < i.start){
                    cur = i;
                }
                else{
                    cur.end = Math.max(cur.end, i.end);
                    it.remove();
                }
            }
            
            return intervals;
        }
    }
    

    Not in-place solution

    class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> ans = new ArrayList<>();
    
            // insert newInterval with ascending order
            int ind = 0;
            while(ind < intervals.size() && intervals.get(ind).start < newInterval.start) ind++;
            intervals.add(ind, newInterval);
    
            // Merge intervals inline
            Interval cur = null;
            for(Interval i : intervals){
                if(cur == null){
                    cur = i;  
                } 
                else if(cur.end < i.start){
                    ans.add(cur);
                    cur = i;
                }
                else{
                    cur.end = Math.max(cur.end, i.end);
                }
            }
            ans.add(cur);
            return ans;
        }
    }
    

Log in to reply
 

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