LeetCode - Insert Interval | Darren's Blog

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16]. This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

遍历已有vector，如果当前interval小于newinterval，插入当前；如果当前interval大于newInterval，则插入newInterval及当前；如果两者重叠，merge以后插入新的interval。
实现中之所以重新new了一个vector来存放结果的原因，是不愿意破坏传入参数。
在原有的vector上面直接修改的话，唯一的区别就是，一旦发现当前interval大于newInterval，就应该return了。

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {

        ArrayList<Interval> result = new ArrayList<Interval>();

        // No interval in the list

        if (intervals == null || intervals.size() == 0) {

            result.add(newInterval);

            return result;

        }

 

        boolean added = false;      // Indicate whether "newInterval" has been added

        // Traverse the (sorted) intervals and merge intervals

        // overlapping with "newInterval" if needed

        for (Interval interval : intervals) {

            if (interval.end < newInterval.start)   // Non-overlapping intervals ahead "newInterval"

                result.add(interval);

            else if (interval.start > newInterval.end) {    // Non-overlapping intervals behind "newInterval"

                // If "newInterval" has not been added, add it before the current interval

                if (!added) {

                    result.add(newInterval);

                    added = true;

                }

                result.add(interval);

            } else {    // Overlapping intervals

                // Merge the current interval with "newInterval", and reflect it in "newInterval"

                newInterval.start = Math.min(newInterval.start, interval.start);

                newInterval.end = Math.max(newInterval.end, interval.end);

            }

        }

        // In case "newInterval" has not been added in the loop

        if (!added)

            result.add(newInterval);

 

        return result;

    }

Code from http://www.programcreek.com/2012/12/leetcode-insert-interval/

     public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
 
        ArrayList<Interval> result = new ArrayList<Interval>();
 
        for(Interval interval: intervals){
            if(interval.end < newInterval.start){
                result.add(interval);
            }else if(interval.start > newInterval.end){
                result.add(newInterval);
                newInterval = interval;        
            }else if(interval.end >= newInterval.start || interval.start <= newInterval.end){
                newInterval = new Interval(Math.min(interval.start, newInterval.start), Math.max(newInterval.end, interval.end));
            }
        }
 
        result.add(newInterval); 
 
        return result;
    }

出题的人，添加了一个附属条件，这些interval是在一个圆环上。比如当环是[1, 255]时，如果两个Interval分别是[1,234], [222, 4], Merge最后的结果是[1,4]。这个条件完全是个干扰，因为如果真的在逻辑中考虑环的话，非常麻烦，而且在环上做循环合并的话，无法判断何时该终止循环。当时我的解法就是，如果第一个是跨越0点的话（比如[234,7]），把它拆分成两个interval（[234, 255],[1,7]）， 然后把[1,7]插到队头，[234,255]插到队尾。 从[1,7]开始往后合并，合并完成后，再检查对头及队尾，需要的话，再合并一次即可。
Read full article from LeetCode - Insert Interval | Darren's Blog