私の問題: 整数軸に配置する n 個の「アイテム」があります。各項目には、整数の閉区間として表される配置のいくつかの選択肢が含まれています。これらの間隔には、重複する要素が含まれる場合があります。目標は、間隔隣接の最大数を持つ int 軸上の n 項目の重複しない配置 (存在する場合) を見つけることです。
上記で使用した用語の詳細: 1) 重複: 区間 [1, 4] と [3, 6] には 2 つの重複要素 {3} と {4} があります。間隔 [2, 5] と [6, 10] は重複しません。2) 間隔の隣接性: 間隔 [a, b] と [b+1, c] は隣接と呼ばれます。この例の間隔隣接の数は 1 です。n 項目の間隔隣接の最大可能数は n-1 です。これは、配置によって n 間隔がペアごとに隣接する場合に発生します。
例: 3 つのアイテムがあります。彼らの配置の選択肢はここにリストされています
item1 has 2 choices: [1, 4], [2, 5]
item2 has 3 choices: [5, 8], [9, 11], [16, 18]
item3 has 2 choices: [3, 5], [13, 15]
実行可能な配置の 1 つは、
[1, 4](item1), [5, 8](item2), [13, 15](item3)
別の 2 つの実行可能な配置は
[1, 4](item1), [16, 18](item2), [13, 15](item3);と
[2, 5](item1), [16, 18](item2), [13, 15](item3).
この例のこれら 3 つの配置はすべて最適です。間隔の隣接数は 1 です。
私の質問: すべての可能性を列挙するよりも良い方法はありますか? あるアイテムの間隔の選択肢が別のアイテムのすべての選択肢と重複する場合、この選択肢を除外できるとしか思えません。どんなアイデアでも大歓迎です:)