ओवरगैपिंग सेगमेंट के सेट द्वारा कवर कुल क्षेत्र की गणना करने के लिए एल्गोरिदम?

Question

मेरे पास अंतराल ओवरलैपिंग के अंत बिंदुओं की एक सूची है, और मैं k=1,2,... (सभी जोड़ी तुलना के बिना) के के अंतराल से कवर कुल क्षेत्र की गणना करने का एक प्रभावी तरीका चाहता हूं। या, क्या यह संभव नहीं है?

उदाहरण के लिए, मान लें कि एक्स शुरू अंक की सूची है, और y समापन बिंदु और उस x[i] < y[i] की सूची है, और

x = (1.5, 2, 3, 5) 
y = (3, 4, 4, 6) 

तो कुल क्षेत्रफल कम से कम एक अंतराल के अंतर्गत आने वाले है कि 3.5, और कम से कम दो तक कवर कुल क्षेत्र 1.

धन्यवाद, पीएच।

Answer 1

यह कम्प्यूटेशनल ज्यामिति से क्लासिक लाइन स्वीप समस्या है।

प्रत्येक प्रारंभ बिंदु पर एक +1 और प्रत्येक अंत बिंदु पर एक -1 रखें। फिर नकारात्मक अनंत से सकारात्मक अनंत तक संख्या रेखा पर चलने की कल्पना करें।

हर बार जब आप +1 का सामना करते हैं, तो अपनी ऊंचाई बढ़ाकर 1. प्रत्येक बार जब आप -1 दबाते हैं, तो अपनी ऊंचाई घटाएं। जैसे ही आप संख्या रेखा पर पी 1 से पी 2 तक जाते हैं, दी गई ऊंचाई से ढकी हुई राशि में पी 2 - पी 1 (लम्बाई घुमावदार) जोड़ें।

तब आपके पास प्रत्येक ऊंचाई से बिल्कुल लंबाई के हिस्टोग्राम होंगे। यदि आप "कम से कम दो अंतराल" मामले को संभालना चाहते हैं तो आप कुल योग जमा कर सकते हैं।

Answer 2

मुझे नहीं पता था कि मैं एक ही चीज़ लिख रहा था, तो मैं अपने समाधान को पोस्ट कर चुका था, इसलिए मैं स्पष्टीकरण छोड़ दूंगा और आपको कोड दूंगा।

// x and y inputs are your start and end points for ranges, 
// as in the example data 
function countOverlapRanges(x, y) { 
    var ranges = []; 
    var n = x.length; 
    if (n !== y.length) { 
     throw "Input arrays must be the same length!"; 
    } 
    var i; 

    // iterate over all inputs, pushing them into the array 
    for (i = 0; i < n; ++i) { 
     ranges.push({ 
      value: x[i], 
      change: 1 
     }); 
     ranges.push({ 
      value: y[i], 
      change: -1 
     }); 
    } 

    // sort the array into number-line order 
    ranges.sort(function (a, b) { 
     return a.value - b.value; 
    }); 

    var result = {}; 
    var k = 1; 
    var maxK = 1; 
    n = ranges.length; 

    // iterate over the sorted data, counting the size of ranges 
    var cur, value, lastValue = ranges[0].value; 
    for (i = 1; i < n; ++i) { 
     cur = ranges[i]; 
     value = cur.value; 
     if (k) { 
      var difference = value - lastValue; 
      result[k] = (result[k] || 0) + difference; 
     } 
     k += cur.change; 
     maxK = Math.max(maxK, k); 
     lastValue = value; 
    } 

    // so far we've counted the ranges covered by exactly k intervals. 
    // adjust the results to get the size of ranges covered by 
    // at least k intervals. 
    var sum = 0; 
    for (i = maxK; i > 0; --i) { 
     sum = result[i] = sum + result[i]; 
    } 

    return result; 
} 

यह एक वस्तु है कि रेखा के साथ दूरी के लिए कश्मीर मूल्यों नक्शे रिटर्न: यह पंक्ति झाडू का एक जावास्क्रिप्ट संस्करण है।