指定された各 N 間隔の右側にある最も近い非重複間隔のインデックスを見つけます。

標準的な間隔表現は、通常、ペアになった開始点と終了点のセットで構成されます。現在のジレンマは、指定された各間隔の右側で最も近い重複しない間隔を見つけることです。このタスクは、現在の間隔と交差しない、または現在の間隔を含まない次の間隔を特定する必要があるため、リソースの割り当てやスケジューリングなど、さまざまなアプリケーションで非常に重要です。

＃＃＃文法＃＃＃

これから示されるコードのデモを理解しやすくするために、まず使用される構文を見てから、アルゴリズムについて詳しく見ていきましょう。

リーリー ＃＃＃アルゴリズム＃＃＃

この問題を解決するには、最も近い重複しないパートナーを指すインデックス スタックを維持しながら、逆の順序で間隔を反復することを中心とした、組織的なアプローチが必要です。ここでは、私たちが提案するアルゴリズムがこの問題を解決する方法の、簡単ですが効果的な手順を示します -

重複しない間隔のインデックスを保存するために空のスタックを作成します。

• 重複しない間隔が見つからなかったことを示すために、間隔の数と同じサイズのインデックス ベクトルを -1 でパディングして初期化します。

• 間隔を右から左に移動します。

• スタックが空ではなく、現在の間隔と最上位の間隔の間に断面積がある場合は、最上位のインデックスをスタックから削除 (ポップ) します。

• 正確な表現を保証するために、スタックが空の場合、現在の間隔を表すベクトル内のインデックス位置に -1 が割り当てられます。これは、右側に重複しない間隔がないことを意味します。 李>

• このタスクを実行する前に、指定したスタックに要素があることを確認することを強くお勧めします。そうでないとエラーが発生します。前記構造上に 1 つ以上の要素があることを確認した後、現在の間隔のベクトルのインデックス値を、特定した構造上の最上位の対応する要素とその対応するインデックス情報と同じに設定することでこれを行うことができます。 . 操作を実行するには、同じ構造体に含めます。

• すべての間隔が処理されるまで、手順 3 ～ 7 を繰り返します。

• インデックス ベクトルを返します。

• ＃＃＃方法＃＃＃

  このジレンマを解決するために、2 つの異なる戦略を検討します。

方法 1: ブルート フォース クラッキング

この問題を解決するために考えられる戦略の 1 つは、暴力を使うことです。基本的に、これには、個々の間隔を調べてから、交差オプションが明らかになるまで、その間隔の右側にあるすべての間隔と比較する必要があります。しかし。この方法を利用すると、時間計算量が O(N^2) になることに注意してください。ここで、N は検査プロセスに参加する間隔の合計数を表します。

＃＃＃文法＃＃＃ リーリー

Example

の中国語訳は次のとおりです:

Example

リーリー ＃＃＃出力＃＃＃ リーリー

方法 2: 最適な解決策

非常に成功したアプローチの 1 つは、最近の重複しない間隔を監視する手段としてスタックを利用することです。このタスクでは間隔を 1 回精査するだけで済むため、この戦略の時間計算量は O(N) です。

＃＃＃文法＃＃＃ リーリー

Example

の中国語訳は次のとおりです:

Example

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

私たちの探索の目標は、指定された各間隔の右側にある最も近い重複しない間隔インデックスの C 内の最適な位置を見つけることです。まず、アルゴリズムを提案し、2 つの潜在的な解決策を提案しながら、構文の複雑さについて詳しく説明します。調査の一環として、総当たりアプローチとスタックベースの最適化アプローチが、テストに成功した実行可能コードに対してどのように機能するかを示します。この方法を使用すると、特定のセットの重複しない最も近い間隔を簡単に特定できます。

以上が指定された各 N 間隔の右側にある最も近い非重複間隔のインデックスを見つけます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。