In place solution, ask for suggestion


  • 4
    J

    I have done non in place insertion. Just want to try in place version because it seems faster and more memory efficient. Would like to ask for suggestion to see whether I can further improve it. Pass OJ already. But not guarantee it's bug free :P

    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        //inplace solution for interval insertion
        if(intervals.empty()){intervals.insert(intervals.begin(),newInterval);return intervals;}
        int l=0,r=(int)intervals.size()-1;
        Interval& n=newInterval;
    
        //binary search for the first interval x, such that x.start is larger than n.start
        while(l<=r){
            int m=(l+r)/2;
            if(intervals[m].start<=n.start)l=m+1;
            else r=m-1;
        }
        int left=l;
        l=0,r=(int)intervals.size()-1;
        //binary search for the first interval x such that x.end is smaller than n.end
        while(l<=r){
            int m=(l+r)/2;
            if(intervals[m].end<n.end)l=m+1;
            else r=m-1;
        }
        int right=r;
    
        //check right boundary
        if(right+1<intervals.size()&&intervals[right+1].start<=n.end)
            n.end=max(n.end,intervals[++right].end);
    
        //check left boundary
        if(left-1>=0&&n.start<=intervals[left-1].end)
            n.start=min(n.start,intervals[--left].start);
    
        //check and update
        if(right+1>=left){
            intervals.insert(intervals.begin()+left,n);
            intervals.erase(intervals.begin()+left+1,intervals.begin()+right+2);
        }
        return intervals;
    }

  • 0
    T
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would better to post as answer with more detail content. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 44
    S

    Mine is not an in-place solution, but I'll put it here anyway in case it would inspire an elegant in-place solution:

    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> ret;
        int i = 0;
        for (i = 0; i < intervals.size(); i++)
        {        
            // If newInterval is BEHIND the current interval
            if (newInterval.start > intervals[i].end) 
                ret.push_back(intervals[i]); // then the current interval goes to the result
            // If new Interval is BEFORE the current interval
            else if (newInterval.end < intervals[i].start) 
            {
                ret.push_back(newInterval); // then new interval goes to the result
                newInterval = intervals[i]; // and save the current interval for later
            }
            else // If newInterval OVERLAPS WITH the current interval
            {
                // Then simply merge the two intervals.
                newInterval.start = min(newInterval.start, intervals[i].start);
                newInterval.end = max(newInterval.end, intervals[i].end);
            }
        }
        // In the end, there will be one interval that is still not stored in the result; and this interval, regardless where it comes from the vector or the newInterval, must be stored in newInterval at this point.
        ret.push_back(newInterval);
        return ret;
    }
    

    This implementation seems to run as fast as yours (both are 56ms in my tests). Although it does use more memory, it does not necessarily perform more data exchange, since the insert and erase operation in your implementation actually involve copying the elements in the vector, one-by-one, to the locations where they should be after insertion or deletion.


  • 2
    V

    Consider this solution: O(log N + M), where M is needed to delete intervals. Worst case still O(N), but it will be faster in average.
    It is not very tricky as it seems to be on first sight :)

       int n = intervals.size();
        
     
        if (n == 0) return vector<Interval>(1,newInterval);
        
        
        int l = 0;
        int r = n-1;
       
        while(l<=r){
            int m = l + (r-l)/2;
            if (intervals[m].start == newInterval.start) {l = m; break;}
            if (intervals[m].start > newInterval.start) r=m-1;
            else l = m+1;
        }
         
        
        int st = l-1;
        
        l = st+1;
        r = n-1;
        while(l<=r){
            int m = l + (r-l)/2;
            if (intervals[m].end == newInterval.end) {l = m+1; break;}
            if (intervals[m].end < newInterval.end) l = m+1;
            else r = m-1;
            
        }
        int en = l;
        
        // if no overlapping
            if (
            (st == -1 || intervals[st].end < newInterval.start) && 
            (en == n || intervals[en].start > newInterval.end) 
        ){
            intervals.insert(intervals.begin() + en, newInterval);
    
        }
        
    
        // if overlap on two      
        if (
            (st != -1 && intervals[st].end >= newInterval.start) && 
            (en != n &&  intervals[en].start <= newInterval.end) 
        ){
            
            intervals[st].end = max(newInterval.end, intervals[en].end);
            intervals.erase(intervals.begin() + en);
        }
        
        //if overlap on lower
        if (
            (st != -1 && intervals[st].end >= newInterval.start) 
        ){
            intervals[st].end = max(newInterval.end, intervals[st].end);
    
         
        }
        
         //if overlap on higher
        if (
            (en != n &&  intervals[en].start <= newInterval.end) 
        ){
                     
         
            intervals[en].start = min(newInterval.start, intervals[en].start);
        }
    
       
        if (en-st-1) intervals.erase(intervals.begin()+st+1,intervals.begin() + en);
        
        
     
        return intervals;
    

  • 1
    Y

    boundary check may be simpler if you choose proper first and last overlapping index

    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        int l = 0, r = intervals.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (newInterval.start == intervals[mid].end) { l = mid; break; }
            else if (newInterval.start > intervals[mid].end) { l = mid + 1; }
            else { r = mid - 1; }
        }
        int start = l;
        r = intervals.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (newInterval.end == intervals[mid].start) { r = mid; break; }
            else if (newInterval.end > intervals[mid].start) { l = mid + 1; }
            else { r = mid - 1; }
        }
        int end = r;
        if (start < intervals.size()) {
            newInterval.start = min(newInterval.start, intervals[start].start);
        }
        if (end >= 0) {
            newInterval.end = max(newInterval.end, intervals[end].end);
        }
        intervals.erase(intervals.begin() + start, intervals.begin() + end + 1);
        intervals.insert(intervals.begin() + start, newInterval);
        return intervals;
    }

  • 7
    R

    Here is my solution in Java. It is in place.

    Idea is to find the lower and upper bound of the newly inserted interval.If lower boundary equals to higher boundary, just insert to that position. Otherwise, compare the values of old intervals and new interval to determine the values of start and end for the interval after insertion.

    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> results = new ArrayList<Interval>();
            if (intervals==null||intervals.size()==0){
                results.add(newInterval);
                return results;
            }
            
            int start=0,end=0;
            
            for (Interval i:intervals){
                if (newInterval.start>i.end) start++;
                if (newInterval.end>=i.start) end++;
                else break;
            }
            
            if (start==end){
                results.addAll(intervals);
                results.add(start,newInterval);
                return results;
            }
            
            for (int i=0;i<start;i++)
                results.add(intervals.get(i));
            Interval interval=new Interval(Math.min(newInterval.start,intervals.get(start).start),Math.max(newInterval.end,intervals.get(end-1).end));
            results.add(interval);
            for (int i=end;i<intervals.size();i++)
                results.add(intervals.get(i));
            return results;
        }
    }

  • 0
    E

    Can't agree more. And BTW, I actually don't think it is a good way to modify the original interval array. The returned value of this function indicates that additional space is surely OK and probably desirable. The cost of insertion and erasion operations on vector should not be ignored.


  • 0
    J

    It's not "in place" if you allocate more space like the result list.


  • 0
    R

    It would be easier to remove intervals in the original list.


  • 0
    J

    that would be "in-place" yes.


  • 1
    P

    Mine is also in place, although I didn't use binary search.

    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        int start = 0, end = 0;
        for (; start < intervals.size() && intervals[start].end < newInterval.start; start++);
        for (end = start; end < intervals.size() && intervals[end].start <= newInterval.end; end++);
        end--;
        if (start <= end && start < intervals.size())
        {
            intervals[start].start = min(intervals[start].start, newInterval.start);
            intervals[start].end = max(intervals[end].end, newInterval.end);
            if (start < end)
                intervals.erase(intervals.begin() + start + 1, intervals.begin() + end + 1);
        }
        else
            intervals.insert(intervals.begin() + start, newInterval);
        return intervals;
    }
    

  • 0
    1

    excellent solution!


  • 0
    S

    this piece of code results.add(intervals.get(i)); will be done in O(1) time if we assume that the List of intervals is given as an ArrayList; if It is given as a linked list, we will need O(n) time for each call of this line; can we assume that the list is given as an ArrayList?


  • 0
    R

    No. Better to use ListIterator


  • 0
    Y

    My simple java solution but it is not in place. The complexity is O(n).

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> res=new ArrayList<>();
            if(intervals==null||intervals.size()<1){
                res.add(newInterval);
                return res;
            }
            res.add(newInterval);
            for(Interval in:intervals){
                int a=res.get(res.size()-1).start;
                int b=res.get(res.size()-1).end;
                if(in.end<a){
                    res.set(res.size()-1,in);
                    res.add(new Interval(a,b));
                }
                else if(b<in.start){
                    res.add(in);
                }
                else{
                    a=Math.min(a,in.start);
                    b=Math.max(b,in.end);
                    res.set(res.size()-1,new Interval(a,b));
                }
            }
            return res;
        }

  • 0
    C

    Great solution! Also we can return once the new interval is appended.

    def insert(self, intervals, newInterval):
        n, ret = newInterval, []
        for index, i in enumerate(intervals):
            if i.end < n.start:
                ret.append(i)
            elif n.end < i.start:
                ret.append(n)
                return ret + intervals[index:]
            else:
                n.start = min(i.start, n.start)
                n.end = max(i.end, n.end)
        ret.append(n)
        return ret
    

  • 0
    U

    Great solution. This is the one to be suggested.


  • 0
    M

    although the "else if" clause make one for loop to solve the problem, I think it is kind of vague. It's better to add another loop to add the remain Intervals than update the newIntervls. Thanks.


  • 0
    C

    @ChuntaoLu, clear code!


Log in to reply
 

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