Мне нужна идея для эффективного алгоритма индекса / поиска и / или структуры данных, чтобы определить, перекрывает ли временной интервал ноль или более временных интервалов в списке, имея в виду, что полное перекрытие является особым случаем частичного перекрытия До сих пор я не придумал ничего быстрого или элегантного ...
Рассмотрим набор интервалов, каждый из которых имеет 2 даты - начало и конец.
Интервалы могут быть большими или маленькими, они могут частично или частично перекрывать друг друга. В нотации Java что-то вроде этого:
interface Period
{
long getStart(); // millis since the epoch
long getEnd();
boolean intersects(Period p); // trivial intersection check with another period
}
Collection<Period> c = new ArrayList<Period>(); // assume a lot of elements
Цель состоит в том, чтобы эффективно найти все интервалы, которые частично пересекают вновь поступивший входной интервал. Для c как ArrayList это может выглядеть как ...
Collection<Period> getIntersectingPeriods(Period p)
{
// how to implement this without full iteration?
Collection<Period> result = new ArrayList<Period>();
for (Period element : c)
if (element.intersects(p))
result.add(element);
return result;
}
Итерирование по всему списку линейно требует слишком большого количества сравнений для достижения моих целей производительности. Вместо ArrayList требуется что-то лучшее для направления поиска и минимизации числа сравнений.
Мое лучшее решение на данный момент заключается в ведении двух отсортированных списков внутри и проведении 4 бинарных поисков и некоторой итерации списка для каждого запроса. Есть идеи получше?
Примечание редактора. Временные интервалы - это особый случай, в котором используются линейные сегменты вдоль одной оси, будь то X или, в данном случае, T (для времени).