この問題にはどのようなアルゴリズムを使用すればよいでしょうか?

Question

最近、ハッカーランクの面接テストで次の問題を正しく解くことができませんでした。プライバシー保護のため、正確な問題名は言いたくないのですが、Google のどこにもこの名前のものが存在しなかったことはわかります。

問題

できるだけ多くの出演者でイベントを開催したいと考えております。出演者の到着予定時刻と公演時間のリストが渡されます。この関数は、競合せずに選択できる出演者の最大数を返す必要があります。

例

N = 5
到着 = [1、3、3、5、7] (出演者はこれらの時間に到着します)
継続時間 = [2, 2, 1, 2, 1] (パフォーマンスを終了するのに必要な時間)
溶液 = 4

したがって、時間 1 で出演者を受け入れることができ、時間 3 で終了します。時点 3 では、2 つの矛盾する選択肢がありますが、どちらを選択したかは問題ではありません。時間 5 と 7 も矛盾しません。

私の解決策

1. zip により到着と期間のタプルを作成しました。最初に到着時にタプルを並べ替え、次に継続時間に従って並べ替えます。
2. 最初から最後までサイクルフォーアイのアウター。各反復で新しいセットを初期化します。
3. j の i から終了までのサイクルの内部。j を競合せずにセットに追加できるかどうかを確認します。設定が最大値より長い場合は保存します。

Python ソース

質問

1. この問題を解決するためのより良い方法、標準アルゴリズムはあるでしょうか?
2. 私のアルゴリズムが機能しない特殊なケースがいくつかあることは承知しています。Hackerrank が私のアルゴリズムを評価したところ、7/13 のテスト ケースのみに合格しました。私が見逃しているいくつかの特殊なケースは何でしょうか?
3. これは検索の問題ですか、それとも最適化の問題ですか?

Answer 1

これは簡単です 間隔スケジュールの最大化 で解決できる問題 O(n log(n)) シンプルな貪欲アルゴリズムによる時間。コツは、パフォーマンスを次のように分類することです。 終了時間 そしてそうではありません 始まる時間.

リンクした Wikipedia ページにある解決策の説明は次のとおりです。

---

いくつかのアルゴリズムは、一見すると有望に見えますが、実際には最適な解決策を見つけられません。

• 最も早く開始する間隔を選択することは最適な解決策ではありません。最も早い間隔がたまたま非常に長い場合、それを受け入れると他の多くの短いリクエストを拒否することになるからです。

• 最短の間隔を選択したり、競合が最も少ない間隔を選択したりすることも最適ではありません。

貪欲な多項式解法

次の貪欲なアルゴリズムは最適な解決策を見つけます。

Select the interval, x, with the earliest finishing time.
Remove x, and all intervals intersecting x, from the set of candidate intervals.
Repeat until the set of candidate intervals is empty.

ステップ 1 で間隔を選択するたびに、ステップ 2 で多くの間隔を削除する必要がある場合があります。ただし、これらの間隔はすべて x の終了時刻と必ず交差するため、すべて相互に交差します。したがって、これらの間隔のうち最大 1 つが最適解に含まれる可能性があります。したがって、最適解のすべての間隔に対して、貪欲な解にも間隔が存在します。これは、貪欲なアルゴリズムが実際に最適な解決策を見つけていることを証明しています。

より正式な説明は次のとおりです。 課金引数.

貪欲なアルゴリズムを時間通りに実行できる O(n log n), 、 どこ n タスクを終了時間で並べ替える前処理ステップを使用したタスクの数です。

---

Answer 2

最大間隔スケジューリング

$ i= 1、\ dotの場合、 $（s_i、t_i）$ を割り当てます。 n $ 、つまり、パフォーマンスは時刻 $ s_i $ で始まり、 $ t_i - s_iの持続時間があります。 $

は、すべての間隔が終了時刻によってソートされるようにします。 単純さのためだけに、すべての時間が明確であると仮定する（この仮定は不要です）。 問題は $ o（n）$ 時刻で解決できます。

$（s_1、t_1）$ を考慮し、 $ i $ を間隔のセットにします。それを交差させる（ $（s_1、t_1）$ 自体を除く）。

は、 $ i $ のすべての間隔が $ t_1 $ を開始する必要があります。それ以外のように、それらは $（s_1、t_1）$ ）とは無関係であり、 $ t_1 $ の後に終了します（それ以外の場合は、 $ t_1 $ は最小終了時刻にはなりません）。これは、 $ i \ cup \ {（s_1、t_1）\} $ のすべての間隔を互いに交差しているため、任意の解決策はそれらのうちの1つを含めることができます。

$ s $ は解決策である（ペアワイトの非交差間隔のサブセット）。 $ s $ をに変換することは常に可能です。="Math-Container"> $（S_1、T_1）$ 、および $ | s '| \ ge | s | $ 。

$ s \ cap i=aftyset $ の場合、 $ s '=を選ぶことができますs \ cup \ {（s_1、t_1）\} $ （ $（s_1、t_1）\ in $ ）

$ s \ cap i \ neq \空の場合$ 、 $（s_i、t_i）$ $ s \ cap i $ の固有の間隔になります。任意の間隔 $（s_j、t_j）\ in \ setminus \ {（s_i、t_i）\} $ のいずれかを満たす必要があります $ S_J> T_I> T_1 $ または $ s_i> t_j> t_1 $ 。後者の場合は実際には $（s_i、t_i）\ in s であるという事実に矛盾するので、実際には不可能です。 つまり、 $（s_i、t_i）$ を置き換えた場合、 $（s_1、t_1）$ 我々はまだ実行可能な解決策を得る。したがって、 $ s '= s \ cup \ {（s_1、t_1）\} \ setminus \ {（s_i、t_i）\} $ 。

下線は、 $（s_1、t_1）$ を含む最適な解決策があることです。そのため、 $（s_1、t_1）$ をソリューションに追加することができます。 $ s \ cup \ { （S_1、T_1）} $ で、残りの間隔の最適な解決策を探します。 これは間隔を順番に考慮した貪欲アルゴリズムを実行し、適合する任意の間隔を追加することになります。

あなたのインスタンスから、開始時間はすでにソートされているようです。この場合、 $（s_i、t_i）$ を変更することによって、「時間を逆にする」というトリック、つまり開始時間と終了時間を交換することができます。 $（ - t_i、-s_i）$ 。 $ o（n）$ を入手できます。 $ \ omomega（n \ log n）$ 時刻を既に必要とする初期ソートステップをスキップして - タイムアルゴリズム。