次の問題を解決するアルゴリズムを作成しようとしています。
入力は、int のペア (キー、値) を含むセットのソートされていないリストです。各ペアの最初のペアはポジティブで、セット内で一意です。
入力セットを分割するアルゴリズムを見つけて、キーごとに値がセットの順序で減少しないようにセットを並べ替えることができるようにしたいと考えています。
セットを個々の値に分割してソートする簡単な解決策があります。分割されるセットの数に関して、より効率的なものが欲しいです。
あなたが遭遇した同様の問題や提案できるテクニックはありますか? 最適な (最小分割数) ソリューションは、多項式時間で可能なように聞こえますか?
編集: この例では、「<=」演算子はセット全体に対する制約を示し、それによって各キー値 (100、101、102) について、対応する値が前のセットの値以上 (または省略されている) になります。セット）。つまり、出力セットからの順序を使用して各キーの値を抽出すると、次のようになります。
- キー 100 {0, 1}
- キー101 {2, 3}
- キー 102 {10, 15}