描述

Given a non-overlapping interval list which is sorted by start point.

Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).
您在真實的面試中是否遇到過這個題？ 是
樣例

Insert (2, 5) into [(1,2), (5,9)], we get [(1,9)].

Insert (3, 4) into [(1,2), (5,9)], we get [(1,2), (3,4), (5,9)].
【思路】
思路很簡單就是定義個result,不斷比較加入到結果集中。
【代碼實現(xiàn)】

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