2017-02-11 3 views
1

私は初年度のプログラミングコースを取っています。これは課題の質問ですので、答えはわかりません。範囲(宿題)に一致する方法を最適化する方法

いくつかの順序付けられた要素のリストが与えられた場合、要素の最大数がスロットに入るように、それらを順序付けられた範囲にどのように配置するのですか?

この例の入力が与えられた(範囲及び要素の数は、必ずしも同じではない):

Elements: 2, 6, 7, 8, 9 
Ranges: 0-3, 2-5, 3-9, 8-10 

このため、出力が3になり、2のようにスロットう2-5(又は0-3 )、6/7は4-9に、9は8-13になる。

私がこれまでに試したことは、貪欲なアプローチを試みることです。 0-7に2最初のスロット

Elements: 2, 5 
Ranges: 0-7, 2-3 

は、要素の処理が、その後5は行き場がない(と、それは検査時に明らかです:それは、例えば、それが動作しない場合が多いと失敗するようです最大値は2です)。 私はどのように進めるべきかはわかりません - ヒントか2つが大いに評価されるでしょう!

+0

最初の例では、答えは2でなければなりません。2-5,3-9を使うことができるので、これらの2つの範囲ですべての数字をスロットに入れることができます。私は正しい? –

+0

また、いくつかのタイプミスもあります。あなたの説明では、例にない範囲を使用しています。 –

答えて

1

maximum bipartite matchingを使用してこの問題を解決できます。

編集: また、範囲を2番目の値で昇順にソートすることもできます。

例: 範囲:0-7、2-3、2-3、0-7

次に、あなたがあなたの貪欲なアプローチを使用することができるだろう。

関連する問題