Short and straight-forward Java solution


  • 221
    S

    Hi guys!

    Here's a pretty straight-forward and concise solution below.

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new LinkedList<>();
        int i = 0;
        // add all the intervals ending before newInterval starts
        while (i < intervals.size() && intervals.get(i).end < newInterval.start)
            result.add(intervals.get(i++));
        // merge all overlapping intervals to one considering newInterval
        while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
            newInterval = new Interval( // we could mutate newInterval here also
                    Math.min(newInterval.start, intervals.get(i).start),
                    Math.max(newInterval.end, intervals.get(i).end));
            i++;
        }
        result.add(newInterval); // add the union of intervals we got
        // add all the rest
        while (i < intervals.size()) result.add(intervals.get(i++)); 
        return result;
    }
    

    Hope it helps.


  • -25
    A

    I don't think this is a good solution, even though it is very short.
    As we learned in data structure class, getting the element at certain index in a list is very time consuming.
    this code calls many times "intervals.get(i)"

    share my code using ListIterator below

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            if(intervals.isEmpty()){
                intervals.add(newInterval);
            }
            ListIterator<Interval> iter = intervals.listIterator();
            boolean started = false;
            while(iter.hasNext()){
                Interval curInterval = iter.next();
                if(!started ){
                    if(overlap(newInterval, curInterval) || overlap(curInterval, newInterval)){
                        started = true;
                        curInterval.start = Math.min(curInterval.start, newInterval.start);
                        curInterval.end = Math.max(curInterval.end, newInterval.end);
                    }
                    else if(curInterval.start > newInterval.end){
                        iter.previous();
                        iter.add(newInterval);
                        iter.next();
                        started = true;
                    }
                }
                else if(started){
                    if(curInterval.start > newInterval.end){
                        break;
                    }
                    else{
                        iter.remove();
                        iter.previous();
                        iter.next().end = Math.max(curInterval.end, newInterval.end);
                    }
                }
            }
            if(!started){
                intervals.add(newInterval);
            }
            return intervals;
        }
        public boolean overlap(Interval v1, Interval v2){
            if((v1.start >= v2.start && v1.start <= v2.end) || (v1.end >= v2.start && v1.end <= v2.end)){
                return true;
            }
            return false;
        }

  • 0
    S

    Hi! Actually, in case of ArrayList get() method will be of a constant time. Anyway, the best and the prettiest in my opinion way above would be to use an array as a result, but leetcode requires to return List and explicit converting would look even more ugly. :)


  • 104
    P

    No need to use additional memory. In place solution with little bit change.

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {``
            int i=0;
            while(i<intervals.size() && intervals.get(i).end<newInterval.start) i++;
            while(i<intervals.size() && intervals.get(i).start<=newInterval.end){
                newInterval = new Interval(Math.min(intervals.get(i).start, newInterval.start), Math.max(intervals.get(i).end, newInterval.end));
                intervals.remove(i);
            }
            intervals.add(i,newInterval);
            return intervals;
    }

  • 0
    S

    Thanks for your solution. it's straight-forward


  • 0

    the big o is O(n). In this question, it removes consecutive intervals (could be 0) and then replace with a new one. The new interval has updated start and end value to merge the intervals.

    To find the first/last intervals to remove, use binary search.

    The big o is O(lgN)


  • 0
    A

    This is darn awesome. Very clean solution!


  • 9
    Z

    You are calling remove() which is O(n) many times (n times in worst case). Not a good idea.


  • 11

    Instead of using new operator, why not just do newInterval.start = . This will make sure you're not creating new objects in a while loop. Great solution though! :)


  • 3
    H

    That is what raise my concern. Since we have no idea what kind of list it is.


  • 4
    D

    remove() function is O(n)


  • 2
    E

    I am a little confused with List Interface. Please help me with this basic Java problem:
    How do you know the input is ArrayList or LinkedList?
    For example, suppose we have the following call

    List<Interval> input1 = new ArrayList<>();
    insert(input1, someInterval);
    
    List<Interval> input2 = new LinkedList<>();
    insert(input2, someInterval);
    

    If it's input1 we can have O(1) access. What about input2?

    The reason why the method is

    public List<Interval> insert(List<Interval> intervals, Interval newInterval)
    

    rather than

    public List<Interval> insert(ArrayList<Interval> intervals, Interval newInterval)
    or
    public List<Interval> insert(LinkedList<Interval> intervals, Interval newInterval)
    

    is because we can have different kinds of lists as input. So we should consider both cases(or all cases that implements List interface) right?

    In this case LinkedList input2 might not have constant update time.

    Please don't down vote me. I am here to learn and hope to be enlightened.


  • 0
    E
    This post is deleted!

  • 0

    I do think it is not obvious for the second loop , it is a little bit difficult for me to think clear by myself.


  • 0
    D

    Do we need to create the Interval every time in the second while loop? I think we can just update the max and min, and create the final interval after the loop, is that a good idea?


  • 1

    This solution is really simply. However I am concerned about time complexity. It is a question frequently asked in real interview and some interviewers expect you do a binary search to locate the insertion position. It is a challenging for me to code the binary search + merging correctly I am wondering if the binary search gives a better time complexity in some cases. The worst case for both methods are O(n). Think about the case that inserted new intervals overlaps with all existing intervals. But what about the case that new interval has no overlapping or it overlaps with O(1) amount of intervals? Is that really O(logn) ? Assuming no overlapping, depending on the implementation of List, if it is an array. we still get O(n). Although we spend O(logn) to locate position, for the inserting, we need to move O(n) intervals. If it is a LinkedList, inserting takes O(1) time but get(i) method takes O(n) time so binary search part takes O(nlogn). Is my analysis correct? Please join me for discussion. If this is reasonable, I can explain to interviewer.


  • 0
    V
    This post is deleted!

  • 2
    O

    remove use O(n) time, so in your case the time complexity can reach O(n2)


  • 2
    H

    c++ version

    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> res;
        int i = 0;
        int n = intervals.size();
        while (i < n&&newInterval.start > intervals[i].end)  res.push_back(intervals[i++]);
        newInterval.start = ((i == n) ? newInterval.start : min(newInterval.start, intervals[i].start));
        while (i < n&&newInterval.end >= intervals[i].start) i++;
        newInterval.end = ((i == 0) ? newInterval.end:max(intervals[i - 1].end, newInterval.end));
        res.push_back(newInterval);
        while (i < n&&newInterval.end < intervals[i].start) res.push_back(intervals[i++]);
        return res;
    }

  • 0
    I

    Do you think the interviewer will be ok with the fact that it uses 3 loops? Ideally wouldnt' you want it to use 1 loop?


Log in to reply
 

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