Short, simple, O(n), in-place, Java solution with explanation


  • 6
    Y

    The idea is to look at each interval in the list. If it intersects with newInterval then merge it to newInterval and delete it. In the end add newInterval back to its corresponding place.

    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            ListIterator<Interval> i = intervals.listIterator();
            Interval in;
            while (i.hasNext()) {
                in = i.next();
                if (newInterval.end < in.start) {
                    i.previous();
                    break;
                }
                if (in.start <= newInterval.end && newInterval.start <= in.end) {
                    newInterval.start = Math.min(newInterval.start, in.start);
                    newInterval.end = Math.max(newInterval.end, in.end);
                    i.previous();
                    i.remove();
                }
            }
            i.add(newInterval);
            return intervals;
        }
    }

  • 0
    H
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    	ListIterator<Interval> i = intervals.listIterator();
        Interval in;
        while (i.hasNext()) {
            in = i.next();
            if (in.end<newInterval.start) {
            	continue;
            }
            if (in.start <= newInterval.end) {
            	newInterval = new Interval(Math.min(newInterval.start, in.start), 
    					Math.max(newInterval.end, in.end));
                i.remove();
            } else {
                i.previous();
                break;
            }
        }
    	i.add(newInterval);
    	return intervals;
    }

  • 0
    J

    beautiful and concise! i really need to make it right when using remove() and privious()/next() of ListIterator.


  • 0
    R
    vector<Interval> insert(vector<Interval>& intervals, Interval t) {
        vector<Interval> result; 
        int i=0;
        bool t_added=false;
        for(i=0; i<intervals.size(); ++i) {
            if(intervals[i].end<t.start)
                result.push_back(intervals[i]);
            else if(intervals[i].start > t.end){
                result.push_back(t);
                t_added=true;
                break;
            }
            else { //update t 
                t.start=min(t.start, intervals[i].start);
                t.end=max(t.end, intervals[i].end);
            }
        }
        if(!t_added) result.push_back(t);
        for(; i<intervals.size(); ++i){
            result.push_back(intervals[i]);
        }
        return result;
    }

Log in to reply
 

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