Inplace and concise(9 lines) Java solution for your reference


  • 3
    X
      public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if(newInterval == null) return intervals;
        int first = 0;
        /*find first overlapping interval*/
        while(first < intervals.size() && newInterval.start > intervals.get(first).end)
            first++;   
        /*merge intervals */
        while(first < intervals.size() && newInterval.end >= intervals.get(first).start)
        {
            newInterval = new Interval(Math.min(newInterval.start,intervals.get(first).start),
                                      Math.max(newInterval.end,intervals.get(first).end));
            intervals.remove(first);
        }
        intervals.add(first,newInterval);
        return intervals;
    }

  • 1
    R

    You can use

            if (intervals.get(overLap).start < newInterval.start) {
    	        newInterval.start = intervals.get(overLap).start;
    	    }
    	    if (intervals.get(overLap).end > newInterval.end) {
    	        newInterval.end = intervals.get(overLap).end;
    	    }
    

    Instead of create new Intervals which saves a lot of time.


  • 1
    Z

    Maybe better to use iterator, the intervals.remove(first); and intervals.add(first,newInterval); would cost O(n) time.


  • 0
    S

    Concise! But the line 'intervals.remove(first);' requires O(n) run time. I suggest you use another list to store the result.


Log in to reply
 

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