Letcode 57挿入間隔

leetcode 57を解決する.Click hereあなた自身を試してみてください!

leetcode問題文

間隔[ i ] = [ starti , endi ]が、i番目の間隔の開始と終わりを表し、間隔がstartiで昇順にソートされます.また、別の間隔の開始と終了を表す間隔newinterval =[ start , end ]も与えられます.
間隔に間隔を入れ替えるように間隔を入れ替えてください.
挿入後の間隔を返します.
例:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

初期思考

ブルートフォース:開始間隔でソートし、すべての残りの間隔をマージし、新しい間隔を押してください.データは既にソートされていますが、これはより効率的にすることができますか?

Draw a timeline diagram for sure. Doing that is one of the most helpful things when solving these interval problems.

破壊する

例を見てみましょう.

これを見ると、間隔を挿入する適切な場所がリストの最初と2番目の間隔の間にあることがわかります.

So to find the insertion point, we have to find the first interval that overlaps with the new interval

つ目の例を見てみましょう.

それで、我々は間隔を反復することによって我々の挿入点を見つけることができて、新しい間隔が我々が繰り返している現在のものと重なっているかどうかチェックすることができます.
挿入の前の間隔がどのようにとどまるかについて注意してください.それらは合併しなければならない.ただし、挿入後のすべての間隔はマージすることができます.

With this in mind, we could iterate through the intervals while there is no overlap with the new interval, and push intervals into a results array. Then we can iterate through the remaining values, merge if necessary, and push into the results array.

それを踏んでみましょう.

ループが終了すると、結果に新しい間隔をプッシュすることができます.

ここからマージ間隔問題に似ています.我々は残りの間隔を繰り返すことができますし、マージする必要があります.あなたがこの問題に慣れていないならば、私は非常にあなたがその最初に取り組むことを勧めます.
後半を踏む


最後に結果を返します.

ニース

アルゴリズム計画

アルゴリズムは3つの部分に分割されます.
第1部
現在の間隔が新しい間隔と重複しない間、

は間隔を通して繰り返します

は間隔を結果配列に押し込む
第2部

、我々は挿入ポイントを見つけました.そして、結果間隔に新しい間隔を押します
第3部

は、残りの間隔

を繰り返します
currentintervalとlastintervalが重なるならば、

マージ間隔

242479182の結果からの

ポップ

は、結果

に合併しました
重複しない場合
に結果に押し込む

増分CurrentDX

最後に、結果を返す
を、それをコード化することができます!

コード

const insert = (intervals, newInterval) => {

    let results = [];
    let currentIdx = 0;

    // Part 1
    while (intervals[currentIdx] && intervals[currentIdx][1] < newInterval[0]) {
        results.push(intervals[currentIdx]);
        currentIdx++;
    }

    // Part 2
    results.push(newInterval);

    // Part 3
    while(currentIdx < intervals.length) {
        let lastInterval = results[results.length - 1];
        let currentInterval = intervals[currentIdx];
        if (lastInterval[1] < currentInterval[0]) {
            results.push(currentInterval);
        } else {
            let merged = [
                Math.min(currentInterval[0], lastInterval[0]),
                Math.max(currentInterval[1], lastInterval[1])
            ]
            results.pop();
            results.push(merged);
        }
        currentIdx++;
    }

    return results;
}

概要

このアルゴリズムの時間計算量はo(n)であり,nはリストの区間数である.私たちが新しいリストを作成しているので、スペース複雑さはO(n)です.
私は最初にこれをしようとするとき、私の頭を包むのは本当に難しいことを覚えています.一般的にインターバル問題で私を助けてきた最大のものは以下のことです.

Non overlapping cases are easier to identify than overlapping cases

これは実装の立場からのキーです.間隔が重ならないかどうか決定するコードを書くのが簡単でなければなりません.あなた自身のためにこれを見る良い方法はいくつかの図を描くことです、そして、2つの間隔が重なることができるすべての方法を識別してください、そして、彼らがそうしなかったすべての方法.
読書ありがとう.これが役に立つという望み!