Insert Interval--LeetCode

ソースリンク:  http://oj.leetcode.com/problems/insert-interval/
 
この問題はMerge Intervalsと一緒です.
似ています.データ構造についてのインターバルの操作です.実は、Merge Intervals
この問題の子操作です.つまりインターバルを挿入して、衝突があったら、mergeを行います.Merge Intervalsと
違うのは、この問題は順序付けが必要ではないです.挿入する前にすでにこれらのintervalsの順序をデフォルトにしました.簡単なのはここで一番多いのは連続して一つだけ衝突があります.基本的な考え方は先にスキャンして新しいintervalの挿入すべき位置に歩いて、次は新しいintervalを挿入して、そして後の衝突を検査して、ずっと新しいintervalのendまで次のintervalのstartより小さいです.そして新しいintervalと現在のintervalの中でendの大きいものを取ってください.一次線形走査を行うため,時間複雑さはO(n)である.空間的にArayListを再作成すれば、O(n)となります.なぜin-placeを操作しないのかという友達がいますが、ArayListというデータ構造を使うと、削除操作は直線的で、このような時間はO(n)ではありません.この問題がLinkdListを使うなら、in-placeができます.時間は線形です.コードは以下の通りです

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    ArrayList<Interval> res = new ArrayList<Interval>();
    if(intervals.size()==0)
    {
        res.add(newInterval);
        return res;
    }
    int i=0;
    while(i<intervals.size() && intervals.get(i).end<newInterval.start)
    {
        res.add(intervals.get(i));
        i++;
    }
    if(i<intervals.size())
        newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
    res.add(newInterval);
    while(i<intervals.size() && intervals.get(i).start<=newInterval.end)
    {
        newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
        i++;
    }
    while(i<intervals.size())
    {
        res.add(intervals.get(i));
        i++;
    }
    return res;
}

この問題には変形があります.挿入する時に衝突を見つけたら、失敗に戻ります.挿入しません.上の問題よりも簡単に見えるようですが、線形スキャンは不要です.二分検索を行います.衝突しないなら、挿入します.そうしないと失敗に戻ります.このように時間複雑度はO(logn)に低減できる.もちろんここでは二分の検索木でこれらのintervalsを維持する必要があります.だから、少しずつ変化して複雑さを下げることができるかもしれません.やはり多く考えるべきです.
また、このようなテーマはOOの設計に関するものについても質問できます.例えば直接にintervalsの種類を実現するには、どのような変数を維持し、どのような機能を実現しますか?これらは面接官と相談して、彼の機能要求に応じてデータ構造を使うことができます.だから拡張性はやはりとても強くて、みんなの考慮の深く入り込むことができます.