Союз интервалов

Question

У меня есть класс, представляющий интервал. Этот класс имеет два свойства «начало» и «конец» сопоставимого типа. Сейчас я ищу эффективный алгоритм для объединения множества таких интервалов.

Заранее спасибо.

Answer 1

Сортируйте их по одному из терминов (например, начало), а затем проверяйте совпадения с соседом (справа) при перемещении по списку.

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

Оказывается, эта проблема была решена, много раз - на разных уровнях фантазии, подпадающих под номенклатуру (ы): http://en.wikipedia.org/wiki/Interval_tree, http://en.wikipedia.org/wiki/Segment_tree, а также 'RangeTree'

(поскольку вопрос ОП включает большое количество интервалов, которые имеют значение для этих структур данных)

---

с точки зрения моего выбора библиотеки Python:

• По результатам тестирования я обнаружил, что больше всего его можно охарактеризовать с точки зрения того, что он является полнофункциональным и текущим питоном (без разбитых битов): классы Interval и Union из SymPy, см .: http://sympystats.wordpress.com/2012/03/30/simplifying-sets/

• Еще один красивый вариант, более высокая производительность, но с меньшим количеством функций (например, не работает при удалении диапазона с плавающей запятой): https://pypi.python.org/pypi/Banyan

Наконец: ищите на самом SO, под любым из IntervalTree, SegmentTree, RangeTree, и вы найдете ответы / зацепки в большом количестве

Answer 3

Использовать алгоритм развертка . По сути, вы сортируете все значения в списке (сохраняя начало или конец интервала вместе с каждым элементом). Эта операция O (n log n). Затем вы за один раз проходите по отсортированным элементам и вычисляете интервалы O (n).

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

Answer 4

Алгоритм geocar не работает, когда:

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

Я не очень уверен, но я думаю, что это правильный путь:

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

Я также реализовал это для вычитания:

#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

Сортировка по всем точкам. Затем просмотрите список, увеличивая счетчик для «начальных» точек и уменьшая его для «конечных» точек. Если счетчик достигает 0, то он действительно является конечной точкой одного из интервалов в объединении.

Счетчик никогда не станет отрицательным и достигнет 0 в конце списка.

Answer 6

Найти сумму объединения интервалов в 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;
}