एल्गोरिथ्म: मर्ज ओवरलैप करने वाले सेगमेंट

Question

मैं एडीटी (पृथक नहीं किया) निम्नलिखित है:

कैसे विलय चरण (उदाहरण हरा तीर बनाने के लिए: List<Segment>

//direction is from 0 to 2pi 
class Segment { 
    int start; 
    int end; 
} 

वे उदाहरण के लिए इस स्थिति का प्रतिनिधित्व)? जाहिर है, मुझे सूची में पुन: प्रयास करने की आवश्यकता है और प्रत्येक खंड सभी अन्य खंडों की तुलना करता है, और प्रत्येक जोड़े के लिए सरल विलय करने के लिए यदि संभव हो तो यह आसान है (यह आसान है)। लेकिन फिर दूसरे पुनरावृत्ति में मुझे किसी भी तरह की सूची की शुरुआत में लौटने और आदि से शुरू करने की आवश्यकता है ... इसलिए मैं यह पता लगाने के लिए संघर्ष करता हूं कि यह एल्गोरिदम कैसे एकत्रित होगा।

संपादित करें: खंडों 0.5pi आदि के लिए 1.75pi से परिपत्र हो सकता है ...

Answer 1

समय शुरू करके सेगमेंट को सॉर्ट करें।

एक स्टैक बनाएं जो मर्ज किए गए अंतराल को संग्रहीत करेगा।

क्रमबद्ध सरणी के पहले तत्व ढेर करने के लिए तो सरणी में प्रत्येक तत्व के लिए तत्व को ढेर

के शीर्ष यदि प्रारंभ समय के अंत समय से अधिक है पर जोड़ें, इसकी तुलना ढेर के शीर्ष पर तत्व, ढेर में अंतराल जोड़ें।

यदि प्रारंभ समय स्टैक के शीर्ष पर तत्व के अंत समय से छोटा है, तो नए तत्व के अंतिम समय से मेल खाने के लिए स्टैक के शीर्ष पर तत्व का अंतिम समय अपडेट करें।

जब संपूर्ण सरणी संसाधित होती है तो परिणामस्वरूप ढेर में मर्ज किए गए अंतराल होते हैं। जावा पर

कार्यान्वयन:

/** 
* Definition for an interval. 
* public class Interval { 
*  int start; 
*  int end; 
*  Interval() { start = 0; end = 0; } 
*  Interval(int s, int e) { start = s; end = e; } 
* } 
*/ 
public class Solution { 
    public List<Interval> merge(List<Interval> intervals) { 
     Deque<Interval> stack = new ArrayDeque<Interval>(); 

     Collections.sort(intervals, new Comparator<Interval>() { 
       public int compare(Interval p1, Interval p2) { 
        return Integer.compare(p1.start, p2.start); 
       } 
      } 
     ); 

     if (intervals.size() < 1) { 
      return intervals; 
     } 
     stack.push(intervals.get(0)); 

     for (int j = 1; j < intervals.size(); j++) { 
      Interval i = intervals.get(j); 
      Interval top = stack.peek(); 
      if (top.end < i. start) { 
       stack.push(i); 
      } 
      else if (top.end < i.end) { 
       top.end = i.end; 
      } 
     } 
     return new ArrayList<Interval>(stack); 

    } 
} 

Answer 2

क्रमबद्ध बिंदु शुरू करने से अपने खंडों।

फिर, प्रत्येक सेगमेंट के लिए, यदि इसका प्रारंभिक बिंदु पिछले सेगमेंट के प्रारंभ और अंत बिंदु के बीच है और इसका अंतिम बिंदु पिछले सेगमेंट के अंत बिंदु से बड़ा है, तो पिछले सेगमेंट के अंत बिंदु को इस सेगमेंट के अंत बिंदु पर सेट करें और वर्तमान सेगमेंट को हटाएं/अनदेखा करें।

यदि वर्तमान खंड पिछले खंड में पूरी तरह से शामिल है, तो बस इसे हटाएं/अनदेखा करें।

इस प्रकार की वजह से O(n log n) है, और आपको सभी अन्य सेगमेंट के साथ प्रत्येक सेगमेंट की तुलना करने की आवश्यकता नहीं है।

सावधान रहें कि आप हटाने या अनदेखा कैसे करते हैं। यह O(1) ऑपरेशन होना चाहिए। उदाहरण के लिए, एक वैरिएबल रखें जो हमेशा पिछले गैर-हटाए गए सेगमेंट को संग्रहीत करता है, और हो सकता है कि हटाए गए सेगमेंट के लिए कुछ झंडा हो ताकि आप जान सकें कि अंत में कौन से एकत्र होंगे। संग्रह पर .remove() संचालन O(n) हो सकते हैं, और आप इससे बचना चाहते हैं।

Answer 3

एक सारिणी में सभी अंतिमबिंदुओं रखो और उन्हें एक polarity (+ तो -) आवंटित। फिर सूची को सॉर्ट करें।

जैसे ही आप मूल्य बढ़ाकर सूची को घुमाते हैं, यह ओवरलैपिंग सेगमेंट के काउंटर को अपडेट करने के लिए पर्याप्त है।

0+ 0.75- 0.5+ 1- 1.25+ 2- 

तो, क्रमित

0+ 0.5+ 0.75- 1- 1.25+ 2- 

मायने रखता है (0 में प्रारंभ)

1 2 1 0 1 0 

इसलिए अंतराल सीमा

0 1 1.25 2 

(संक्रमण 0 to >0 या >0 to 0 पर) देता है 10

---

यह भी अतिरिक्त झंडे बिना यथा-स्थान, विशुद्ध रूप से किया जा सकता है।

आप start और end मूल्यों को अलग-अलग क्रमबद्ध करें, जगह में (Segments को पूरी तरह से स्थानांतरित न करें); इस तरह polarities अंतर्निहित रहते हैं।

फिर सूची को दो क्रमबद्ध सूचियों (दो स्वतंत्र इंडेक्स का उपयोग करके) के विलय के रूप में पार करें, और ओवरलैप काउंटर बनाए रखें। आप सीमाओं को जगह में ओवरराइट कर सकते हैं, क्योंकि विलय के परिणाम में अधिक अंतराल नहीं होते हैं।

से

[0 0.75][0.5 1][1.25 2] 

शुरू दोनों सूचियों गलती से पहले से ही हल कर रहे हैं।

0 0.5 1.25 (+) 
0.75 1 2 (-) 

मर्ज के लिए आगे बढ़ें, जो आदेश

+ + - - + - 

और अंतिम परिणाम प्राप्त किया जाता है में तत्वों का चयन करेंगे स्थानांतरण मूल्यों

[0 1][1.25 2][x x] 

---

से संबंधों के मामले में सीमाओं पर, + और - को क्रम में संसाधित करना बेहतर है जैसे y कहां दो बराबर सीमाओं को उत्सर्जित करने से बचें।

Answer 4

मैं परिपत्र के दृष्टिकोण के अन्य उत्तरों में जोड़ूंगा, यानी यदि आपके पास 2pi से अधिक लूपिंग हैं तो आपको क्या करना चाहिए।

इसे संभालने के दो तरीके हैं। एक ऐसा है कि प्रत्येक ऐसे सेगमेंट को दो में विभाजित करें: एक जहां से 2pi तक जा रहा है, दूसरा शून्य से कहीं भी जा रहा है। इसके बाद, समस्या को हल करें जैसे कि यह परिपत्र नहीं है, और फिर यदि आपके पास शून्य से शुरू होने वाला सेगमेंट है, और एक सेगमेंट 2pi पर समाप्त होता है, तो बस उन्हें मर्ज करें।

एक दूसरा दृष्टिकोण विशेष रूप से यवेस डाउस्ट के उत्तर के लिए है। आपको केवल इतना पता होना है कि कितने सेगमेंट शून्य बिंदु को कवर करते हैं (आप आसानी से इसकी गणना कर सकते हैं); इसके बाद, आप शून्य के साथ "गणना" प्रारंभ नहीं करते हैं, लेकिन कवर खंडों की इस संख्या के साथ।