मर्ज skylines, फूट डालो और

Question

मैं (gif देखें) प्रसिद्ध क्षितिज समस्या को हल करने की कोशिश कर रहा हूँ को जीत:

इनपुट

(1,11,5), (2,6, 7), (3,13,9), (12,7,16), (14,3,25), (1 9, 18,22), (23,13,29), (24,4,28)

लौटने चाहिए, अंक हैं कि पीछे अन्य इमारतों चला जाना चाहिए और Y- अक्ष में परिवर्तन का निर्देशांक लौटने क्षितिज में होना चाहिए:

(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (1 9, 18), (22, 3), (23 , 13), (29, 0)

मैं के रूप में O (n एलजी n का चलने का समय प्राप्त करने के लिए तो एक विभाजन का उपयोग करके दृष्टिकोण एल्गोरिथ्म के लिए करते हैं और जीत के लिए) की कोशिश कर रहा हूँ, लेकिन मैं कर रहा हूँ विलय भाग पर फंस गया।

हर बार जब मैं इसके बारे में सोचता हूं तो मुझे भ्रमित हो जाता है। उदाहरण के लिए, मैं जांचता हूं कि स्काइलाइन पहले कौन सा है। जिसमें निचला एक्स-समन्वय होता है, फिर मैं इसे जोड़ता हूं + यह मेरी नई स्काईलाइन पर हाइट है। लेकिन फिर मुझे दो अन्य स्काइलाइनों के पीछे एक आकाशगंगा मिलती है, मैं इस 'टक्कर' का पता कैसे लगा सकता हूं?

क्या मैं पहली बार जांचता हूं कि स्किलाइन्स के पास बाएं.एक्स 2 < right.x1 की जांच करके कोई ओवरलैप है या नहीं? लेकिन फिर मुझे लगता है कि मुझे पहले क्या देखना चाहिए? एक्स-अक्ष पर प्राथमिकता का ओवरलैप और सबकुछ एक बड़ा चिकन-अंडे की गड़बड़ी में बदल जाता है।

शायद मैं बहुत जटिल सोच रहा हूं? मुझे जो चाहिए वह उच्चतम वाई निर्देशांक का सेट है, हर चौराहे पर, क्या मुझे इस तरह से संपर्क करना चाहिए?

Answer 1

मुझे लगता है कि यह एक दृष्टिकोण है एक सिर के चारों ओर लपेट के लिए आसान है कि किया जाना चाहिए: प्रत्येक आयत के लिए शुरू और खत्म वस्तुओं में

• स्प्लिट एक्स निर्देशांक, इस प्रकार है:

  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))
• आयताकारों का एक (आंशिक रूप से खाली) सेट बनाएं (जिसे वाई-समन्वय द्वारा क्रमबद्ध किया जाएगा, उदा।एक BST)
• लूप इन वस्तुओं के माध्यम से (जो अब अनुसार क्रमबद्ध क्रम में) (O(n))
  • जब भी एक शुरुआत का सामना करना पड़ा है
    • (आयतों के सेट O(log n))
    • को आयत जोड़ें तो यह है नई उच्चतम आयत, उत्पादन (O(1))
  • जब भी कोई खत्म सामना करना पड़ा है करने के लिए है कि प्रारंभ बिंदु जोड़ने
    012 यदि यह उच्चतम आयताकार
    • आयतों (O(log n))
    • के सेट से आयत निकालें, सेट में अगले सर्वोच्च आयत खोजने के लिए और उत्पादन (O(1)) (यदि सेट खाली है, (current.finishX, 0) जोड़ने के लिए बिंदु (current.finishX, new.y) जोड़ने उत्पादन के बजाय) के लिए

तो O(n log n)।

Answer 2

यह मर्ज सॉर्ट के लिए एल्गोरिदम को संशोधित करके हासिल किया जा सकता है। क्षितिज के लिए एल्गोरिथ्म की तरह दिखता है:

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); 
    } 
    }