Java solution with explanation of algorithm


  • 0
    L

    Since the list is already sorted, our insert should be based on comparison. Additionally, once we insert, it may change the entire list afterwards. We may use placeholders to define if we are done with the merge and subsequent elements may be directly inserted, or keep code shorter by making the current element as the newinterval for comparison. Take a look at the simple O(N) Java code.

        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> result = new ArrayList<>();
            for(Interval cur : intervals) {
                if(cur.start>newInterval.end) {//cur starts after new.
                    //insert the new interval.
                    result.add(newInterval);
                    //we could have inserted cur as well but that will make 
                    //merge complex. Just carry this as newInterval for further 
                    //iteration to help merge.
                    newInterval = cur;
                }
                else if(newInterval.start > cur.end) { //cur happens before.
                    result.add(cur);
                }
                else { //some sort of overlap.
                    newInterval.start = Math.min(newInterval.start,cur.start);
                    newInterval.end = Math.max(newInterval.end,cur.end);
                }
            }
            //add the newinterval that may be missing.
            result.add(newInterval);
            return result;
        }
    

Log in to reply
 

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