Расчет количества перекрывающихся интервалов в O (n) времени?

Question

Рассмотрите список перечней форм (start, end). Интервалы уже отсортированы в списке по их компоненту start.

Мой вопрос в том, есть ли способ рассчитать для каждого разного интервала, сколько интервалов будет перекрываться с ним, в O(n) времени.

Я представляю несколько вариантов, работающих в O(n lg n) времени, но мне было любопытно относительно ограничения O(n).

Например, O(n lg n) решения будет:

1. Добавить все значения start и end к массиву A и сортировку массива (так что мы сейчас в O(n lg n) области *), устраняя любые дубликаты в процессе.
2. Из этого массива A создать массив R регионов (N-1 регионов с R[i] = (A[i], A[i+1])).
3. Теперь это всего лишь вопрос итерации по массиву интервалов и увеличение значения всех связанных с ним областей. Это делается в O(n).

* Ну, если бы мы знали, что интервалы были плотно упакованы в небольшой области мы могли бы использовать счетный род и которые приносят бы нас вниз обратно O(n), но это не кажется хорошим предположением для общего случая ,

Любой способ улучшить это до O(n)?

Answer 1

Пусть каждый интервал i обозначается как s_i,e_i (start_i, end_i).

Я могу показать алгоритм, O(nlogk), где k есть максимальное число интервалов, пересекающая (s_i,s_{i+1}) - для некоторого i.
В худшем случае k находится в O(n), он улучшает производительность для более разреженных интервалов.

Мы будем использовать мини-кучу для хранения интервалов при повторении списка, минимальная куча будет сортироваться в соответствии с конечным значением (e_i).

Идея состоит в том, чтобы перебирать список по стартовому началу и подсчитывать количество интервалов, которые были замечены, но конечное значение было выше интервала.

Псевдокод (с объяснениями):

h = new min heap //sorted by end value 
h.push (-infinity,infinity) //add a dummy interval for avoiding dealing with empty heap cases 
res = 0 
for each interval (s_i,e_i) in ascending order of s_i: 
     //push out all already "expired" intervals: 
     while (heap.min() < s_i): 
      heap.pop() 
     // at this point, all intervals in the heap: 
     // 1. started before s_i 
     // 2. finish after s_i 
     // thus, each of them is intersecting with current interval. 
     res = res + heap.size() - 1 //-1 for removing dummy interval (-inf,inf) 
     heap.push(e_i) 
return res 

Временная сложность:

• кучи размером не более k на каждом шаге (как определено выше).
• Каждый интервал выталкивается один раз и удаляется один раз, каждый O (logk).
• Итого: O(nlogk).

Корректность:

претензии:

Два интервала (s_i, e_i) и (s_j, e_j) пересекает, если и только если:

s_i <= s_j <= e_i OR s_j <= s_i <= e_j 

Доказательство просто путем проверки всех возможностей для двух интервалов (у нас есть 4!/(2!2!)=6 возможностей с s_i<=e_i, s_j<=e_j)

(1) s_i <= e_i <= s_j <= e_j   - no overlap 
(2) s_j <= e_j <= s_i <= e_j   - no overlap 
(3) s_j <= s_i <= e_i <= e_j   - overlap, and condition meets 
(4) s_i <= s_j <= e_j <= e_j   - overlap, and condition meets 
(5) s_j <= s_i <= e_j <= e_i   - overlap, and condition meets 
(6) s_i <= s_j <= e_i <= e_j   - overlap, and condition meets 

Назад к доказательству:

Итак, мы знаем, что если два интервала пересекается, при встрече второй из них (пусть это будет (s_i,e_i)), первый (s_j,e_j) все еще находится в куче, так как s_i <= e_j , и мы добавим пересечение (s_i,e_i) с номером (s_j,e_j). Мы знаем, что это также правильная вставка, потому что мы уже видели s_j, поэтому мы знаем s_j <= e_j <= s_i, и по вышеуказанному требованию - это действительно пересекающийся интервал.

Кроме того, поскольку для каждого пересекающихся интервалов (s_i,e_i) и (s_j,e_j), мы гарантированы, что (s_j,e_j) все еще находится в куче при обработке (s_i,e_i) (сверху претензии, и так как мы никогда не будет удалить его, потому что для каждого k мы уже обработанные: s_k <= s_i <= e_j -> e_j >= s_k), гарантируется, что пересечение (s_j,e_j) и (s_i,e_i) будет подсчитано, когда мы добавим размер кучи во втором обходном интервале.

QED

Малое предположение: Не уверен, что это ручки дубликаты хорошо, должны заботиться об этих крайних случаях внимательно глядя на < и <= сравнивают.

Python код:

intervals = [(0,3.5),(1,2),(1.5,2.5),(2.1,3),(4,5)] 
#5 overlaps 
def findNumOverlapping(intervals): 
    import heapq 
    h = [] 
    heapq.heappush(h, 10000) #infinity 
    res = 0 
    for (s,e) in intervals: 
     while (heapq.nsmallest(1, h)[0] < s): 
      heapq.heappop(h) 
     res = res + len(h) - 1 
     heapq.heappush(h,e) 
    return res 

Answer 2

Не с помощью алгоритма сравнения на основе. (Скорее всего, этот аргумент можно распространить на алгебраические деревья решений фиксированной степени, но это сделает его намного более техническим.)

Как и при сортировке, ключ должен заметить, что при n! возможности для выхода, мы не сможем работать быстрее, чем lg n! = Theta (n log n), каждый из которых дает один бит (при условии невырожденного ввода, который, поскольку мы обсуждаем нижнюю границу здесь, находится под нашим контролем, поэтому не является предположением вообще). Вот алгоритмы кодирования/декодирования. (Формальное доказательство оставляется в качестве упражнения.)

Encoding: input is a1, ..., an such that aj in {1, ..., n + 1 - j} 
      output is overlap counts c1, ..., cn of some instance 

For j = 1 to n, 
    Add an interval (j, j + aj - 1/2) 
For j = 1 to n, 
    Output the overlap count cj of the interval beginning at j 

Decoding: input is overlap counts c1, ..., cn. 
      output is a1, ..., an 

For j = 1 to n, 
    Initialize cj' = cj 
For j = 1 to n, 
    Set aj = cj' + 1 
    For k = j + 1 to j + cj', 
     ck' = ck' - 1 

С небольшими изменениями этот аргумент доказывает асимптотическую оптимальность алгоритма Амит в параметра к.