最大不連続集合の集合

Question

3つの数の集合の集合を考えると、最大の不連続集合を見つける。例えば、C = {（3,4,5）、（4,5,6）、（1,2,3）、（6,9,10）、（7,8,9）}とする。最大の独立集合は{（1,2,3）、（4,5,6）、（7,8,9）}であるので、この入力は3を返すべきです。どのようにして最大の分離集合の集合を出力するプログラムを書くことができますか？

私はすべての5つのセットを選択して開始することを考えました。次に、各セットを見て、その要素を削除することが残りのセットに影響するかどうかを確認します。私たちが（3,4,5）を奪うと、（4,5,6）と（1,2,3）を保つことができます。したがって、その純便益は+1です。最終的なリストから削除する必要があります。それから、もし私たちが（4,5,6）を奪うと、私たちはそれを（6,9,10）保つことができます。正味利益は0なので、それを削除しないでください。削除（1,2,3）は何も影響しません。削除しないでください。 （6,9,10）を削除すると、私たちは（7,8,9）を維持することができます。それが意味をなさないか分からないが、私があなたの考えを知らせてください！

Answer 1

3つの数字が常に連続している場合は、簡単な動的プログラミングソリューションがあります（再帰式を使用して数字1..iを使用して配置できる最大セットを計算します）。

ただし、この制約が常に真ではない場合、この問題はNP困難です。 NP完全3-dimensional matching problemを解決するために使用できるので、NP困難です。

たとえば、X、Y、Zの要素が一致しているとします。私たちは、数字1を使って、許容される各試合のセットを構築することができます。| X | | X | + 1 .. | X | + | Y | | X | + | Y | .. | X | + | Y | + | Z |第3の位置にある。これらの集合を構成したら、この問題を解くアルゴリズムを使って3次元のマッチング問題を解くことができます。

Answer 2

貪欲にします。トリプレットが実際の間隔であることに注意してください、ミッド数は問題ではありません、唯一の開始/終了のもの（すなわち[start, whatever, end]に間隔は関係の順序を使用してO(N log(N)) greedy solution

1. ソートwhatever

   を無視します：

   • 場所終わりに向かって高い端部を有するもの（つまり、「ある[スタート_私は、エンド_私は] < _I <端 _J "等しい末端に
   • 、より長いものはつまり（高い "" IFF" 終了[ _{J J}、エンド起動]を[開始 _I、エンド] <スタックを取る「IFF "i" は _J <開始_を開始）

2. [ _Jを開始]と「 _K開始」場合下向きソート間隔をスキャン

3. の最後のセグメントをプッシュ

   • （kインデックスが現在のものである）（「_{スタックトップ}開始」よりも高い、すなわちcurr間隔でより多くのスペースを確保できます）、スタックの一番上をポップして現在のスタックをプッシュします。
   • >「_{スタックトップ}を起動する」IF「 _Kを終了」 - 現在のスタックの頂部と重ならない - 単にスタック内の現在の間隔を押し（ソリューションの一部です）。
   • そうでない場合は、現在の間隔を無視し、最後には

を（私たちはこれまで持って最善の解決策と重なって、我々はそれを失いたくない貪欲である）、あなたは最大カウントを持っています重なり合っていないセグメントのうちスタック上の最も左上のもの、つまりO（N）の空間複雑さです。
これを数えるだけでよい場合は、スタックの先頭だけが比較に含まれているので、スタックの先頭を覚えておく必要があります（スタックのトップ/現在のものと比較してcountを変更しないでください;あなたがたった今「スタックトップ」を置き換えてカウントを増やす）。したがって、カウントする空間の複雑さはO（1）だけです。

---

あなたの例：

1. 仕分け工程の後に、あなたは{（1,2,3）、（3,4,5）、（4,5,6としてあなたの間隔を持っています）、（7,8,9）、（6,9,10）}

2. top of stack（6,9,10） - 以下のすべてのステップは、サイクルのアンロールです。

3. （7,8,9） - より控えめな開始、古いスタックからの追い出し、現在の（新しいもの）の押し込み - スタックの先頭（7,8,9）、カウント= 1。

4. （4,5,6） - スタックの先頭より早く終了します。スタックトップ（4,5,6）、count = 2;

5. （3,4,5） - 開始が小さいが、スタックの先頭と重なっている。貪欲で - 無視/捨てる。スタックトップ（4,5,6）、カウント= 2;

6. （1,2,3） - スタックの先頭より早く終了します。スタックトップ（1,2,3）、count = 3;下方サイクルの

エンドは、スタックは、上から下への読み出し：{（1,2,3}、（4,5,6）、（7,8,9）}の数と3.

---

C++（をテストしていません）

struct interval { int s; int e; } 

struct comparator { 
    bool operator(const interval& i1, const interval& i2) const { 
    int i=i1.e-i2.e; // higher ends placed last 
    if(0==i) { // higher length/lower starts will be higher 
     i=i2.s-i1.s; 
    } 
    return i<0; 
    } 
} 

int count_intervals(std::vector<interval>& sets) { 
    if(sets.empty()) return 0; 

    comparator comp; 
    std::sort(sets.begin(), sets.end(), comp); 

    /* if you need the solution as well, use a stack */ 
    // std::stack<std::vector> solution; 
    interval& stack_top=sets[sets.size()-1]; // solution.push(stack_top); 
    int count=1; // we have at least one in the stack 
    for(int i=sets.size()-2; i>=0; i--) { 
    interval& curr=sets[i]; 
    if(curr.s > stack_top) { // a better one, lets more room in front 
     stack_top=curr; // solution.pop(); solution.push(curr); 
    } 
    else if(curr.e < stack_top.s) { 
     stack_top=curr; // solution.push(curr); 
     count++; 
    } 
    } 
    // if you need the solution, arrange the params of the function to return it 
    return count; 
}