データ構造と区間マージアルゴリズム、貪欲

[[439314]]

マージ間隔

LeetCode の問題へのリンク: https://leetcode-cn.com/problems/merge-intervals

一連の間隔が指定されている場合、重複するすべての間隔を結合します。

例1:

入力: 間隔 = [[1,3],[2,6],[8,10],[15,18]]
出力: [[1,6],[8,10],[15,18]]
説明: 区間 [1,3] と [2,6] は重複しているので、[1,6] にマージします。

例2:

入力: 間隔 = [[1,4],[4,5]]
出力: [[1,5]]
説明: 区間 [1,4] と [4,5] は重複区間とみなすことができます。
注: 入力タイプは 2019 年 4 月 15 日に変更されました。新しいメソッドシグネチャを取得するには、デフォルトのコード定義をリセットしてください。

ヒント：

間隔[i][0] <= 間隔[i][1]

アイデア

この質問は分類する必要があると誰もが感じているはずですが、左の境界で分類するべきでしょうか、それとも右の境界で分類するべきでしょうか?

大丈夫だよ！

次に、左の境界でソートし、ソート後にローカル最適性が達成されます。つまり、マージするたびに最大の右の境界が取られるため、より多くの間隔をマージでき、全体的な最適性が達成されます。つまり、重複する間隔をすべてマージします。

局所最適性は、全体最適性につながる可能性があります。反例が見つからない場合は、貪欲法を試してください。

すると、何人かの生徒が「最大の右の境界を結合すべきではないですか? これは貪欲とどう関係があるのですか?」と尋ねました。

欲は常識になることもあるよ！ハハ

左境界で小さいものから大きいものの順にソートした後、intervals[i][0] < intervals[i - 1][1]、つまり、intervals[i] 左境界 < intervals[i - 1] 右境界の場合、intervals[i] の左境界は intervals[i - 1] の左境界以上でなければならないため、繰り返しが存在することになります。

つまり、intervals[i]の左境界がintervals[i - 1]の左境界と右境界の範囲内にある場合、繰り返しが存在するはずです。

これは少し抽象的ですが、図を見てください: (図の間隔は左の境界でソートされていることに注意してください)

マージ間隔

重複を判断する方法がわかったら、あとはマージするだけです。マージ間隔をシミュレートするにはどうすればよいでしょうか?

実際には、間隔を新しい間隔として結合した後、左と右の境界を使用して、それを結果配列に追加するだけです。マージがない場合は、元の間隔を結果配列に追加します。

C++ コードは次のとおりです。

クラスソリューション{
公共：
    // 区間の左端を小さい順から大きい順に並べ替える
静的ブール cmp (const ベクトル< int >& a, const ベクトル< int >& b) {
 a[0] < b[0]を返します。
    }
    ベクトル<ベクトル< int >> merge(ベクトル<ベクトル< int >>& 間隔) {
        ベクトル<ベクトル< int >> 結果;
        if ( intervals.size () == 0)結果を返します。
        ソート(intervals.begin (), intervals.end (), cmp) ;
        bool flag = false ; // 最後の間隔が結合されているかどうかをマークします
int長さ = 間隔.サイズ( ); 
 
 ( int i = 1; i < 長さ; i++) {
 int start = intervals[i - 1][0]; // 最初はi-1間隔の左境界
整数  end = intervals[i - 1][1]; // 初期 i-1 間隔の右境界
            while (i < length && intervals[i][0] <= end ) { // 間隔をマージする
end = max ( end , intervals[i][1]); // 右の間隔を継続的に更新する
                if (i == length - 1) flag = true ; // 最後の区間もマージされる
                i++; // 次の区間のマージを続行する
            }
            // startとendはintervals[i - 1]の左と右の境界を表すので、最適なintervals[i]のintervalがマージされているかどうかをマークする必要があります
            結果.push_back({start, end });
        }
        // 最後の区間が結合されていない場合は結果に追加します
        if (フラグ == false ) {
            result.push_back({intervals[length - 1][0], intervals[length - 1][1]});
        }
結果を返します。
    }
 };

もちろん、上記のコードは少し冗長なので、次のように最適化できます。（考え方は同じです）

クラスソリューション{
公共：
    ベクトル<ベクトル< int >> merge(ベクトル<ベクトル< int >>& 間隔) {
        ベクトル<ベクトル< int >> 結果;
        if ( intervals.size () == 0)結果を返します。
        // ソートパラメータはラムダ式を使用する
        ソート( intervals.begin (), intervals.end (), [](const vector< int >& a, const vector< int >& b){ return a[0] < b[0];}) ; 
 
        結果.push_back(間隔[0]);
 ( int i = 1; i < intervals.size ( ) ); i++) {
            if (result.back()[1] >= intervals[i][0]) { // 間隔をマージする
                result.back()[1] = max (result.back()[1]、間隔[i][1]);
            }それ以外{
                結果.push_back(間隔[i]);
            }
        }
結果を返します。
    }
 };

時間計算量: O(nlogn)、クイックソートあり
空間計算量: O(1)、結果配列(戻り値に必要なコンテナが占める空間)は計算しませんでした。

要約する

貪欲アルゴリズムに関して、多くの学生は次のように考えています。「常識に基づいて直接実行できれば、貪欲を使っているとは感じないだろう。一度直感的に理解できなければ、永遠に理解できないかもしれない。」

「Code Random Thoughts」コースを受講した人は、貪欲になるのは難しい、本当に難しいということを経験したはずです。

それで何をすべきでしょうか?

私の貪欲シリーズの冒頭で「貪欲アルゴリズムについて、知っておくべき！」と説明したように、貪欲アルゴリズムにはルーチンやフレームワークがないため、さまざまな従来のソリューションはより多くの露出と練習を必要とし、自然に思い浮かぶようになります。

「Code Thoughts」では、古典的で一般的な貪欲な質問を取り上げます。あなたがしなければならないのは、一生懸命勉強してチェックインすることだけです。

その他の言語

ジャワ

クラスソリューション{
公共  int [][] merge( int [][] 間隔) {
        リスト< int []> res = new LinkedList<>();
        配列.sort(intervals, (o1, o2) -> Integer .compare(o1[0], o2[0])); 
 
 int開始 = 間隔[0][0];
 ( int i = 1; i < 間隔.長さ; i++) {
            （間隔[i][0] > 間隔[i - 1][1]）の場合{
                res.add (新しいint []{start, intervals[i - 1][1]});
                開始 = 間隔[i][0];
            }それ以外{
                間隔[i][1] = Math.max (間隔[i][1]、間隔[i - 1][1]);
            }
        }
        res.add (新しいint []{start、intervals[intervals.length - 1][1]});
 res.toArray(新しいint [ res.size ()][]);を返します。
    }
 }

 // バージョン 2
クラスソリューション{
公共  int [][] merge( int [][] 間隔) {
        LinkedList< int []> res = new LinkedList<>();
        配列.sort(intervals, (o1, o2) -> Integer .compare(o1[0], o2[0]));
        res.add (間隔[0]);
 ( int i = 1; i < 間隔.長さ; i++) {
            （間隔[i][0] <= res.getLast()[1]）の場合{
 int start = res.getLast()[0];
整数 終了= Math.max (間隔[i] [ 1]、res.getLast()[1]);
                res.removeLast();
                res.add (新しいint []{start, end });
            }
それ以外{
                res.add (間隔[i]);
            }
        }
 res.toArray(新しいint [ res.size ()][]);を返します。
    }
 }

パイソン

クラスソリューション:
    def merge(self, intervals: List[List[ int ]]) -> List[List[ int ]]:
        len(intervals) == 0の場合:間隔を返す
        間隔.sort(キー=lambda x: x[0])
        結果 = []
        結果.append(間隔[0])
 iが範囲(1, len(間隔))内にある場合:
最後= 結果[-1]
            last [1] >= intervals[i][0]の場合:
                結果[-1] = [最終[0],最大値(最終[1], 間隔[i][1])]
それ以外：
                結果.append(間隔[i])
結果を返す

行く

func merge(intervals [][] int ) [][] int {
    // 小さい順から大きい順に並べ替える
    sort.Slice(intervals,func(i,j int )bool{
間隔[i][0]<間隔[j][0]を返す
    })
    // もう一度繰り返す
i:=0;i<len(intervals)-1;i++{の場合
        間隔[i][1]>=間隔[i+1][0]の場合{
            intervals[i][1]= max (intervals[i][1],intervals[i+1][1]) // 最大値を割り当てる
            間隔=追加(間隔[:i+1]、間隔[i+2:]...)
            私  -  
        }
    }
戻り間隔
}
関数max (a,b int ) int {
    a>b{の場合
返す
    }
 bを返す
}

ジャバスクリプト

var merge =関数(間隔) {
    間隔をソートします((a, b) => a[0] - b[0]);
    prev = 間隔[0]とする
    結果 = []
 ( i =0 とします; i<intervals.length; i++){
        cur = intervals[i]とする
        現在の[0] > 前の[1]){
            結果.push(前)
            前 = 現在
        }それ以外{
            prev[1] = Math.max (cur[1],prev[1])
        }
    }
    結果.push(前)
結果を返す
};

バージョン2: 左と右の間隔

/**
 * @param {number[][]} 間隔
 * @return {数値[][]}
 */
 var merge =関数(間隔) {
    n = intervals.lengthとします。
    n < 2の場合、間隔を返します。
    間隔をソートします((a, b) => a[0]- b[0]);
    res = []とします。
左= 間隔[0][0]、
右= 間隔[0][1];
 ( i = 1; i < n; i++ とします) {
        （間隔[i][0] >右）の場合{
            res.push([左,右]);
左= 間隔[i][0];
右= 間隔[i][1];
        }それ以外{
右= Math.max (intervals[i][1],右) ;
        }
    }
    res.push([左,右]);
 resを返します。
 };