Facebook脸书面试题：插入区间的解决方法及复杂度分析

/**

 * Definition of Interval:

 * public classs Interval {

 *     int start, end;

 *     Interval(int start, int end) {

 *         this.start = start;

 *         this.end = end;

 *     }

 */







public class Solution {

    /*

     * @param intervals: Sorted interval list.

     * @param newInterval: new interval.

     * @return: A new interval list.

     */

    public List insert(List intervals, Interval newInterval) {

        List newIntervals = new ArrayList();

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

            newIntervals.add(newInterval);

        }

        for (int i = 0; i
            // 如果新区间的结束值小于区间开始值，插在这里，后面续上

            if (newInterval.end
                newIntervals.add(newInterval);

                for (int j = i; j
                    newIntervals.add(intervals.get(j));

                }

                break;

            }

            // 如果新区间的开始值大于区间结束值，把当前区间加进去

            else if (newInterval.start > intervals.get(i).end) {

                newIntervals.add(intervals.get(i));

            }

            // 出现交叉，需要合并

            else {

                newInterval.start = Math.min(newInterval.start, intervals.get(i).start);

                newInterval.end = Math.max(newInterval.end, intervals.get(i).end);

            }

            // 最后只剩一个数据了，添加进去

            if(i == intervals.size() - 1){

                newIntervals.add(newInterval);

            }

        }

        return newIntervals;

    }

}