固定数の教室を与えられた重み付けされた間隔スケジューリングの変動

Question

私は、固定数の教室を考慮した重み付き間隔のスケジューリング問題の解決について質問をしました。最初は、開始時間と終了時間を持つ間隔のセットが与えられ、それぞれには重みが設定されています。だから、問題の目的は、重さを最大にする2つの教室でスケジューリングを見つけることです。動的なプログラミングでこれを行う効率的な方法はありますか？

私のアプローチは、各教室の間隔を単純に最大化するアルゴリズムを構築しているので、簡単でした。これを行うより良い方法はありますか？

Answer 1

私の考えは、完全に動的なプログラミングではありません。しかし、私はそれが助けになると思います。

1. すべてのクラスを開始時刻でソートします。
2. クラスの場合i次のクラスを見つけるjこの開始時刻はこの終了時刻よりも大きいか等しい。
3. （私たちは開始時間でソートされてソートされた配列を持っているので、あなたがこれを見つけることができますバイナリ検索を使用すると）max_so_farが配列され、[z]は、すべてのについて
4. を最後にZからmax_weightクラスが含まれているmax_so_far想定します私は、[i]は、クラスの重量の合計の最大値を見つけ、重量はmax_so_far [J]

このコードのコードhere 時間の複雑さはO（nLog（N））でご覧ください。