5

私は有名なスカイラインの問題を解決しようとしています（gifを参照）：

入力

（1,11,5）、（2,6,7）、（3,13,9）、（12,7,16）、（14,3,25）、（19,18,22）、（23 、13,29）、（24,4,28）

戻る必要がある場合は、他の建物の背後にあるポイントがなくなり、Y軸の変化の座標が戻るスカイラインにある必要があります。

（1、11）、（3、13）、（9、0）、（12、7）、（16、3）、（19、18）、（22、3）、（23、13）、（29 、0）

O（n lg n）の実行時間を達成するために、アルゴリズムに分割統治アプローチを使用してこれを実行しようとしていますが、マージ部分で立ち往生しています。

それについて考えるたびに私は混乱します。たとえば、最初にスカイラインがどれであるかを確認します。たとえば、X座標が低い方を確認してから、その+その高さを新しいスカイラインに追加します。しかし、他の2つのスカイラインの背後にあるスカイラインに遭遇した場合、この「衝突」をどのように検出できますか？

最初に、left.x2 <right.x1かどうかをチェックして、スカイラインにオーバーラップがあるかどうかをチェックしますか？しかし、私は最初に何をチェックすべきだと思いますか？x軸の優先順位が重なると、すべてが大きな鶏卵の混乱に変わります。

多分私はあまりにも複雑だと思っていますか？必要なのは、すべての交差点での最高のy座標のセットですが、このようにアプローチする必要がありますか？

4

2 に答える 2

8

これは、頭を包み込むのが簡単なアプローチだと思います。

  • 次のように、x座標を各長方形の開始オブジェクトと終了オブジェクトに分割します。

    rect(x1, y, x2) -> (x1, y, "start", reference to rect),
                   (x2, y, "finish", reference to rect)

    だから次のようなもの：

    class MyStruct
{
   Rectangle rect;
   int x, y;
   bool isStart;
}
  • これらのオブジェクトをx座標（O(n log n)）で並べ替えます
  • （最初は空の）長方形のセットを作成します（これはy座標で並べ替えられます（例：BST）） 。
  • これらのオブジェクトを（現在ソートされている順序で）ループします（O(n)）
    • スタートに遭遇したときはいつでも
      • 長方形のセットに長方形を追加します（O(log n)）
      • それが新しい最も高い長方形の場合は、その開始点を出力に追加します（O(1)）
    • 仕上げに遭遇したときはいつでも
      • 長方形のセットから長方形を削除します（O(log n)）
      • 最も高い長方形の場合は、セット内で次に高い長方形を見つけて(current.finishX, new.y)、出力にポイントを追加します（O(1)）（セットが空の場合は、(current.finishX, 0)代わりに出力に追加します）

だからO(n log n)。

于 2013-02-20T11:06:28.033 に答える
0

これは、マージソートのアルゴリズムを変更することで実現できます。スカイラインのアルゴリズムは次のようになります。

ConstructSkyLine

    ConstructSkyLine(List B ) --------------- O(nlogn)
    {
        If(B.size() == 1)
        {
            List skyLineList = new List();
            SKYLINE = new SKYLINE(B.XL, B.XR, B.H);
            skyLineList.add(SKYLINE);
            Return skyLineList;
        }
        B1, B2 <-- Split(B);
        List S1 <-- ConstructSkyLine(B1);
        List S2 <-- ConstructSkyLine(B2);
        List S <-- MergeSkyline(S1, S2);
        Return S;
    }

MergeSkyline

    MergeSkyline(List S1, List S2) --------------- O(n)
    {
        List< SKYLINEENTRY> skylineEntryList = new ArrayList<SKYLINEENTRY>();
        while (S1.isEmpty() && S2.isEmpty())--------------- O(n)
        {
           S1Item <-- S1.get(0);
           S2Item <-- S2.get(0);
           If (S1Item.XL < S2Item.XL)
           {
             Merge(S1, S2, skylineEntryList);   --------------- O(n)
           }
           Else
           {
             Merge(S2, S1, skylineEntryList); --------------- O(n)
           }
         }

         If(!S1.isEmpty())
         {
            skylineEntryList.add(S1);
         }

         If(!S2.isEmpty())
         {
           skylineEntryList.add(S2);
         }
         Retrun skylineEntryList;
      }

マージ 

  Merge(S1, S2, skylineEntryList) --------------- O(n)
  {
    SKYLINEENTRY <-- null;
    S1Item <-- S1.get(0);
    S2Item <-- S2.get(0);
    SKYLINEENTRY.XL = S1Item.XL;
    If(S1Item.XR > S2Item.XL) // means over lap 
    {
        If(S1Item.H > S2Item.H) // S1 is higher.
        {
           SKYLINEENTRY.XR = S1Item.XR;
           SKYLINEENTRY.H = S1Item.H;
           S1.remove(S1Item); --------------- O(n)
           skylineEntryList.add(SKYLINEENTRY);
           if(S2Item.XR < S1Item.XR) // full overlap
           {
              S2.remove(S2Item); --------------- O(n)
           }
           Else // partial overlap
           {
              S2Item.XL <-- S1Item.XR;
           }            
        }
        Else //S2 is higher
        {
           SKYLINEENTRY.XR = S2Item.XL;
           SKYLINEENTRY.H = S1Item.H;
           if(S2Item.XR < S1Item.XR) // full overlap with S2
           {
              S1Item.XL = S2Item.XR;
           }
           Else // partial overlap
           {
              S1.remove(S1Item); --------------- O(n)
           }    
           skylineEntryList.add(SKYLINEENTRY);  
        }   
     }
     Else // no overlap
     {
        SKYLINEENTRY.XR = S1Item.XR;
        SKYLINEENTRY.H = S1Item.H;
        S1.remove(S1Item); --------------- O(n)
        skylineEntryList.add(SKYLINEENTRY);
     }
  }
于 2015-02-09T15:15:35.537 に答える