Thuật toán để tính tổng diện tích được bao phủ bởi một tập hợp các phân đoạn chồng chéo?

Question

Tôi có một danh sách các điểm cuối của các khoảng thời gian chồng chéo nhau và tôi muốn một cách hiệu quả để tính tổng diện tích được bao phủ bởi khoảng k, cho k=1,2,... (mà không thực hiện tất cả so sánh từng cặp). Hoặc, điều này là không thể?

Ví dụ, giả sử x là danh sách các điểm bắt đầu, và y là danh sách các điểm kết thúc, và x[i] < y[i] đó, và

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

sao cho tổng diện tích bao phủ bởi ít nhất một khoảng thời gian là 3,5 và tổng diện tích được bao phủ bởi ít nhất hai là 1.

cảm ơn, ph.

Answer 1

Đây là vấn đề quét dòng cổ điển từ hình học tính toán.

Đặt +1 ở mỗi điểm bắt đầu và -1 ở mọi điểm cuối. Sau đó, tưởng tượng đi bộ trên dòng số từ vô cực âm đến vô cùng tích cực.

Mỗi khi bạn gặp +1, tăng chiều cao của bạn lên 1. Mỗi lần bạn nhấn -1, giảm chiều cao của bạn. Khi bạn di chuyển từ p1 đến p2 trên dòng số, thêm p2 - p1 (chiều dài được quét) vào số tiền được bao phủ bởi chiều cao đã cho.

Sau đó, bạn sẽ có một biểu đồ độ dài được bao phủ chính xác theo từng chiều cao. Bạn có thể tích lũy tổng số nếu bạn muốn xử lý "ít nhất hai khoảng thời gian" trường hợp.

Answer 2

Tôi không biết @rrenaud đã đăng giải pháp của mình trong khi tôi đang viết cùng một thứ, vì vậy tôi sẽ bỏ qua phần giải thích và chỉ cung cấp cho bạn mã. Đây là phiên bản quét dòng javascript:

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

Nó trả về một đối tượng ánh xạ k giá trị đến khoảng cách dọc theo dòng.