Liên hiệp các khoảng thời gian

Question

Tôi có một lớp đại diện cho một khoảng thời gian. Lớp này có hai thuộc tính "bắt đầu" và "kết thúc" của một loại so sánh. Bây giờ tôi đang tìm kiếm một thuật toán hiệu quả để có sự kết hợp của một tập hợp các khoảng thời gian như vậy.

Xin cảm ơn trước.

Answer 1

Sắp xếp chúng theo một trong các thuật ngữ (bắt đầu, ví dụ), sau đó kiểm tra chồng chéo với hàng xóm (bên phải) của nó khi bạn di chuyển qua danh sách.

class tp(): 
    def __repr__(self): 
     return '(%d,%d)' % (self.start, self.end) 
    def __init__(self,start,end): 
     self.start=start 
     self.end=end 
s=[tp(5,10),tp(7,8),tp(0,5)] 
s.sort(key=lambda self: self.start) 
y=[ s[0] ] 
for x in s[1:]: 
    if y[-1].end < x.start: 
     y.append(x) 
    elif y[-1].end == x.start: 
     y[-1].end = x.end 

Answer 2

Sử dụng thuật toán sweep line. Về cơ bản, bạn sắp xếp tất cả các giá trị trong một danh sách (trong khi vẫn giữ cho dù đó là bắt đầu hoặc kết thúc của khoảng thời gian cùng với mỗi mục). Hoạt động này là O (n log n). Sau đó, bạn lặp trong một lần đi dọc theo các mục được sắp xếp và tính toán các khoảng thời gian O (n).

O (n log n) + O (n) = O (n log n)

Answer 3

Sắp xếp tất cả các điểm. Sau đó đi qua danh sách tăng bộ đếm cho điểm "bắt đầu" và giảm số điểm đó cho điểm "kết thúc". Nếu bộ đếm đạt đến 0, thì nó thực sự là điểm cuối của một trong các khoảng thời gian trong liên minh.

Bộ đếm sẽ không bao giờ bị âm và sẽ đạt đến 0 ở cuối danh sách.

Answer 4

Thuật toán bởi geocar thất bại khi:

s=[tp(0,1),tp(0,3)] 

Tôi không phải là rất chắc chắn nhưng tôi nghĩ rằng đây là cách chính xác:

class tp(): 
    def __repr__(self): 
     return '(%.2f,%.2f)' % (self.start, self.end) 
    def __init__(self,start,end): 
     self.start=start 
     self.end=end 
s=[tp(0,1),tp(0,3),tp(4,5)] 
s.sort(key=lambda self: self.start) 
print s 
y=[ s[0] ] 
for x in s[1:]: 
    if y[-1].end < x.start: 
     y.append(x) 
    elif y[-1].end == x.start: 
     y[-1].end = x.end 
    if x.end > y[-1].end: 
     y[-1].end = x.end 
print y 

Tôi cũng thực hiện nó cho phép trừ:

#subtraction 
z=tp(1.5,5) #interval to be subtracted 
s=[tp(0,1),tp(0,3), tp(3,4),tp(4,6)] 

s.sort(key=lambda self: self.start) 
print s 
for x in s[:]: 
    if z.end < x.start: 
     break 
    elif z.start < x.start and z.end > x.start and z.end < x.end: 
     x.start=z.end 
    elif z.start < x.start and z.end > x.end: 
     s.remove(x) 
    elif z.start > x.start and z.end < x.end: 
     s.append(tp(x.start,z.start)) 
     s.append(tp(z.end,x.end)) 
     s.remove(x) 
    elif z.start > x.start and z.start < x.end and z.end > x.end: 
     x.end=z.start 
    elif z.start > x.end: 
     continue 

print s 

Answer 5

Nó chỉ ra p này roblem đã được giải quyết, nhiều lần - ở mức độ khác nhau của ưa thích, đi dưới danh pháp (s): http://en.wikipedia.org/wiki/Interval_tree, http://en.wikipedia.org/wiki/Segment_tree, và cũng 'RangeTree'

(như câu hỏi OP của liên quan đến số lượng lớn khoảng những datastructures quan trọng)

---

về sự lựa chọn của riêng tôi lựa chọn thư viện python:

• Từ thử nghiệm, tôi thấy rằng những gì hầu hết móng tay nó về được đầy đủ tính năng và trăn hiện tại (không bit mục nát) : các ' Các lớp Interval 'và' Union 'từ SymPy, xem: http://sympystats.wordpress.com/2012/03/30/simplifying-sets/

• Một lựa chọn tốt khác, tùy chọn hiệu suất cao hơn nhưng ít tính năng phong phú hơn (ví dụ: đã không hoạt động trên phạm vi nổi loại bỏ điểm): https://pypi.python.org/pypi/Banyan

Cuối cùng: tìm kiếm xung quanh về SO bản thân, dưới bất kỳ IntervalTree, SegmentTree, RangeTree, và bạn sẽ tìm thấy câu trả lời/móc thêm galore

Answer 6

Để tìm tổng số liên kết của khoảng thời gian bằng C++

#include <iostream> 
#include <algorithm> 

struct interval 
{ 
    int m_start; 
    int m_end; 
}; 

int main() 
{ 
    interval arr[] = { { 9, 10 }, { 5, 9 }, { 3, 4 }, { 8, 11 } }; 

    std::sort(
     arr, 
     arr + sizeof(arr)/sizeof(interval), 
     [](const auto& i, const auto& j) { return i.m_start < j.m_start; }); 

    int total = 0; 
    auto current = arr[0]; 
    for (const auto& i : arr) 
    { 
     if (i.m_start >= current.m_end) 
     { 
      total += current.m_end - current.m_start; 
      current = i; 
     } 
     else if (i.m_end > current.m_end) 
     { 
      current.m_end = i.m_end; 
     } 
    } 

    total += current.m_end - current.m_start; 
    std::cout << total << std::endl; 
}