Поскольку интервалы являются потоковыми, они должны быть сохранены в некоторой коллекции, которая эффективна для
- вставка новых интервалов
- Нахождение интервалов перекрытия
- объединение перекрывающихся интервалов при добавлении новых интервалов
Операция объединения должна учитывать следующие случаи
без перекрытия вставка (7, 9) в [(1, 5), (10, 15)] дает [(1,5), (7, 9), (10,15)]
некоторое перекрытие вставка (4, 6) в [(1, 5), (10, 15)] дает [(1,6), (10,15)]
перекрытие моста вставка (4, 11) в [(1, 5), (10, 15), (20, 30)] дает [(1, 15), (20, 30)]
максимальное перекрытие вставка (1, 20) в [(2, 5), (7, 9), (13, 15)] дает [(1, 20)]
полное перекрытие вставка (5, 6) в [(1, 7), (10, 19)] дает [(1, 7), (10, 19)]
и множество промежуточных случаев и варианты того, что указано выше
В конце операции вставки эта коллекция должна содержать только непересекающиеся интервалы. Очевидно, что сохранение этих непересекающихся интервалов, отсортированных в этом наборе, необходимо для эффективного поиска и объединения пересекающихся интервалов. Любое несортированное решение будет требовать поиска каждый интервал каждый раз, когда что-нибудь вставлено, и затем повторять этот процесс каждый раз, когда происходит слияние. Помня, что элементы должны оставаться отсортированными, любой тип хеширования или неупорядоченная структура данных также не помогут нам. Лучшее, что мы можем здесь сделать, это O(nlgn).
Используя отсортированный массив (или его варианты с массивами или векторами), один из подходов может заключаться в бинарном поиске начала нового вставленного интервала, затем в левом и правом поиске и объединении, где необходимо. Это приведет к O(nlgn) для поиска места размещения элемента, однако вставка в середину массива и удаление элементов из массива требует повторной индексации каждого элемента в массиве каждый раз, когда происходит вставка или слияние. Это слишком дорогая операция, она плохо масштабируется, а также сводит на нет цель сохранения отсортированных элементов в ущерб производительности наивного несортированного решения.
Одним из способов решения проблемы вставки / удаления является использование отсортированного связанного списка , где вставки и удаления являются дешевыми, однако это сделает бинарный поиск очень неэффективным, если не невозможным, а также приведет к поражению цели. сохранения отсортированных элементов, что опять ухудшает производительность наивного несортированного решения.
Стоит исследовать интервальные деревья , определенные в википедии, однако эта структура данных не объединяет интервалы, она может только запрашивать их, поэтому это также не поддерживает наш вариант использования.
Лучший способ - использовать двоичное дерево для хранения интервалов, где интервал имеет определенный метод сравнения , который возвращает, что элементы равны, если есть какое-либо перекрытие. Это позволяет очень эффективно находить перекрывающиеся интервалы за O(lgn) времени.
Пример класса сравнения выглядит следующим образом
public class Interval<T extends Comparable<T>> implements Comparable<Interval<T>>
{
private final T start_;
private final T end_;
public Interval(final T start, final T end)
{
this.start_ = start;
this.end_ = end;
}
@Override
public int compareTo(Interval other) {
if (other.start_.compareTo(this.end_) == -1) {
return -1;
} else if (other.start_.compareTo(this.end_) == 1) {
return 1;
} else {
return 0;
}
}
}
Набор деревьев (или набор, или любой из его вариантов) может быть расширен или составлен так, чтобы соответствовать операции вставки. Обратите внимание: я использую вариант treemap, поскольку java не позволяет возвращать элемент в наборе.
public class IntervalCollection
{
private Map<Interval, Interval> intervalCollection_ = new TreeMap<>();
public void insert(Interval interval)
{
while (intervalCollection_.containsKey(interval)) {
Interval other = intervalCollection_.get(interval);
intervalCollection_.remove(interval);
interval = new Interval(Math.min(interval.start_, other.start_),
Math.max(interval.end_, other.end_));
}
intervalCollection_.put(interval, interval);
}
}
Этот сборник использует возможности языка для выполнения большей части тяжелой работы за вас и обеспечивает эффективную вставку и объединение для потоковых интервалов.