Insert Interval

給一個排序過的 Interval 數組，插入一個新的 interval，如果有重疊要合併

看似簡單的一題，但如果程式功力不好會不知道怎麼寫...

像我就會想到將新的 interval 對數組進行遍歷，遇到要合併的就合併為一個新的 interval，

下一步我就不會了，因為不知道要怎麼使用新的 interval，我不知道要怎麼把合併過的跟下一個比較

因為合併的比較是 newInterval.start <= interval.end ，如果我在遍歷時合併，那合併後的 start 一定小於下一個的 end

這樣不對，應該是要記住插入的位置，等到合併後的 end 小於下一個的 start ，表示無法合併

20190204

突然會寫了

跟 merge interval 一樣，只是要多幾個條件

 public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    List<Interval> result = new ArrayList<>();
    if (intervals == null || intervals.size() == 0) {
        result.add(newInterval);
        return result;
    }

    Interval comp = newInterval;
    for (int i=0; i<intervals.size(); i++) {
        Interval temp = intervals.get(i);
        if (comp.end < temp.start) {
            result.add(comp);
            comp = temp;
        } else if (comp.end == temp.start) {
            comp.end = temp.end;
        } else if (comp.start <= temp.end) {
            comp.start = Math.min(comp.start, temp.start);
            comp.end = Math.max(comp.end, temp.end);
        } else if (comp.start > temp.end) {
            result.add(temp);
        }
    }
    result.add(comp);
    return result;
}

另一個方法是，先 insert 後再開始 merge，這樣速度會比較快

insert 的點是找到第一個比 newInterval.start 還要大的地方

merge 迴圈可以這樣想，因為我們要從第一個開始比，所以需要一個「比較的對象」

那可以給個空值

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    List<Interval> result = new ArrayList<>();
    if (intervals == null || intervals.size() == 0) {
        result.add(newInterval);
        return result;
    }

    int idx = 0;
    while (idx < intervals.size() && newInterval.start > intervals.get(idx).start)
    {
        idx++;
    }
    intervals.add(idx, newInterval);

    Interval last = null;
    for (Interval in : intervals) {
        if (last == null || in.start > last.end) {
            result.add(in);
            last = in;
        } else {
            last.end = Math.max(last.end, in.end);
        }
    }
    return result;
}