@@ -0,0 +1,1490 @@
+/***%0A * Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).%0A *%0A * You may assume that the intervals were initially sorted according to their start times.%0A *%0A * Example 1:%0A * Given intervals %5B1,3%5D,%5B6,9%5D, insert and merge %5B2,5%5D in as %5B1,5%5D,%5B6,9%5D.%0A *%0A * Example 2:%0A * Given %5B1,2%5D,%5B3,5%5D,%5B6,7%5D,%5B8,10%5D,%5B12,16%5D, insert and merge %5B4,9%5D in as %5B1,2%5D,%5B3,10%5D,%5B12,16%5D.%0A *%0A * This is because the new interval %5B4,9%5D overlaps with %5B3,5%5D,%5B6,7%5D,%5B8,10%5D.%0A */%0A/**%0A * Definition for an interval.%0A * public class Interval %7B%0A *     int start;%0A *     int end;%0A *     Interval() %7B start = 0; end = 0; %7D%0A *     Interval(int s, int e) %7B start = s; end = e; %7D%0A * %7D%0A */%0Aimport java.util.List;%0A%0Apublic class Solution %7B%0A    // Solution : O(n) O(1)%0A    public List%3CInterval%3E insert(List%3CInterval%3E intervals, Interval newInterval) %7B%0A        int i = -1;%0A        while(++i %3C intervals.size()) %7B%0A            if (newInterval.end %3C intervals.get(i).start) %7B%0A                intervals.add(i, newInterval);%0A                return intervals;%0A            %7D else if (newInterval.start %3E intervals.get(i).end) %7B%0A                continue;%0A            %7D else %7B%0A                newInterval.start = Math.min(intervals.get(i).start, newInterval.start);%0A                newInterval.end = Math.max(intervals.get(i).end, newInterval.end);%0A                intervals.remove(i--);%0A            %7D%0A        %7D%0A        intervals.add(intervals.size(), newInterval);%0A        return intervals;%0A    %7D%0A%7D%0A

add InsertInterval.java