Вопрос
У меня есть класс, представляющий интервал.Этот класс имеет два свойства "start" и "end" сопоставимого типа.Сейчас я ищу эффективный алгоритм для объединения набора таких интервалов.
Заранее благодарю.
Решение
Сортируйте их по одному из терминов (например, начало), а затем проверяйте совпадения с соседом (справа) при перемещении по списку.
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
Другие советы
Используйте строчную линию . По сути, вы сортируете все значения в списке (сохраняя начало или конец интервала вместе с каждым элементом). Эта операция O (n log n). Затем вы за один раз проходите по отсортированным элементам и вычисляете интервалы O (n). Р>
O (n log n) + O (n) = O (n log n)
Оказывается, эта проблема решалась много раз - на разном уровне фантазии, в рамках номенклатуры: http://en.wikipedia.org/wiki/Interval_tree , http://en.wikipedia.org/wiki/Segment_tree , а также "RangeTree"
(поскольку вопрос OP включает в себя большое количество интервалов, эти структуры данных имеют значение)
с точки зрения моего собственного выбора библиотеки python:
Из тестирования я нахожу, что то, что больше всего подходит с точки зрения полнофункциональности и актуальности python (не бит-гнилой) :классы 'Interval' и 'Union' из SymPy см. : http://sympystats.wordpress.com/2012/03/30/simplifying-sets/
Еще один привлекательный вариант, более производительный, но менее многофункциональный (напр.не сработало при удалении диапазона с плавающей запятой) : https://pypi.python.org/pypi/Banyan
Наконец-то:поищите на SO itself, в любом из IntervalTree, SegmentTree, RangeTree, и вы найдете ответы / хуки в еще большем количестве
Алгоритм 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
Сортировка всех точек. Затем просмотрите список, увеличивая счетчик для «начала». баллы и уменьшая его для "конца" точки. Если счетчик достигает 0, то он действительно является конечной точкой одного из интервалов в объединении.
Счетчик никогда не станет отрицательным и достигнет 0 в конце списка.
Чтобы найти сумму объединения интервалов в 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;
}