Приоритет совпадений диапазонов дат

Question

Я нашел похожие проблемы вокруг, но никто не рассматривал приоритет.

R : (------------|xxxxxxx|ooo|xx|----------------) (---) 

S1: (------------)    (----------------) (---) 
S2:  (xxxxxxxxxxxxxxx) (xxxxxx) 
S3:     (ooooooo)   (oo) 

Скажем, у меня есть 3 источника диапазонов дат, с именами S1, S2 и S3 с приоритетами 1,2 и 3 соответственно (1 самый высокий) и результат Р. Мне нужен результат, чтобы быть не -ограничение диапазонов дат, где приоритет имеет наивысший приоритет.

Я думал о решении, но он довольно последователен. Сначала я создать таблицу, упорядоченную по возрастанию даты, по убыванию приоритетов (в случае даты столкновений, наивысший приоритет идет первым в таблице) с их ID и действия (открытого или близкого расстояния):

ID | Action | Priority | Date | 
-------------------------------- 
S1a | Open | 1  | 1 | 
S2a | Open | 2  | 2 | 
S1a | Close | 1  | 3 | 
S3a | Open | 3  | 4 | 
S2a | Close | 2  | 5 | 
S2b | Open | 2  | 6 | 
S3a | Close | 3  | 7 | 
S1b | Open | 1  | 8 | 
S2b | Close | 2  | 9 | 
S3b | Open | 3  | 10 | 
S3b | Close | 3  | 11 | 
S1b | Close | 1  | 12 | 
S1c... 

Тогда я начинаю переборе эта таблица и заполнить упорядоченный список и таблицу результатов:

Так первая строка будет выглядеть так:

Order List:   Result: 
ID | Priority |  ID | Action | Date | 
S1a| 1  |  S1a| Open | 1 | 

Второй ряд, добавляет дату открытия S2a, но ничего не писать, потому что больше приоритета существует в стол:

Order List:   Result: 
ID | Priority |  ID | Action | Date | 
S1a| 1  |  S1a| Open | 1 | 
S2a| 2  |  

Третья строка, закрывающая S1a, записывает дату закрытия, а так как S2a перемещается в верхнюю часть списка, она также записывает дату открытия для S2a.

Order List:   Result: 
    ID | Priority |  ID | Action | Date | 
x S1a| 1  |  S1a| Open | 1 | 
    S2a| 2  |  S1a| Close | 3 | 
         S2a| Open | 3 | 

Я думаю, вы можете увидеть, где это происходит ... Много перекрестную проверку и т.д., но в статье, кажется, работает. Я могу объяснить алгоритм немного лучше, если кому-то это нужно, но я не думаю, что это трудно понять. Если в упорядоченном списке есть более высокий приоритет, он ничего не пишет. При удалении более высокого приоритета снова открывается следующий самый большой.

Может быть, кто-нибудь с лучшей, более конкретной идеей?

Спасибо за ваше время!

Answer 1

Другим способом для этого было бы построить его в обратном порядке, начиная с заполнения таблицы с наименьшим приоритетом и просто перезаписывая даты, когда вы заполняете ее более высокоприоритетными элементами. Это связано с необходимостью создавать список заказов и отслеживать, какие элементы открыты, чтобы их можно было запустить.

Примечание: Я должен сказать, фронт, что следующий алгоритм почти наверняка менее эффективен (я не делал математику, но интуиция подсказывает мне, это менее эффективно). Это просто еще один способ приблизиться к проблеме .

Было бы более выгодно таким образом группировать даты открытия и закрытия каждого события. Для простоты я буду ссылаться на дату начала до даты окончания как «событие». Итак, вы начинаете с добавления каждого события с самым низким приоритетом. Затем вы начинаете просматривать данные, организованные по приоритету, а затем по дате.Как так:

ID | Action | Priority | Date | 
-------------------------------- 
S3a | Open | 3  | 4 | 
S3a | Close | 3  | 7 | 
S3b | Open | 3  | 10 | 
S3b | Close | 3  | 11 | 
S2a | Open | 2  | 2 | 
S2a | Close | 2  | 5 | 
S2b | Open | 2  | 6 | 
S2b | Close | 2  | 9 | 
S1a | Open | 1  | 1 | 
S1a | Close | 1  | 3 | 
S1b | Open | 1  | 8 | 
S1b | Close | 1  | 12 | 
------------------------------- 

Так просто пройти через очень низкий приоритет и добавить все к результату:

РЕЗУЛЬТАТ:

ID | Action | Priority | Date | 
-------------------------------- 
S3a | Open | 3  | 4 | 
S3a | Close | 3  | 7 | 
S3b | Open | 3  | 10 | 
S3b | Close | 3  | 11 | 

Это где самое интересное, теперь вы начинаете глядя на события для следующего наивысшего приоритета. Таким образом, мы сталкиваемся с нашим первым событием S2a, что мы делаем, мы ищем даты в результате, которые лежат между и S2a Close. Если мы подумаем абстрактно на мгновение, мы получим 3 разных случая:

1. Мы находим начало события.
2. Мы находим окончание события.
3. Мы находим начало и конец события.

В первом случае, поскольку начало события будет перенесено в конец события с более высоким приоритетом. Это означает, что события, связанные с событием, начинаются с Close текущего события с более высоким приоритетом.

Во втором случае, поскольку окончание события происходит после начала события с более высоким приоритетом, оно должно заканчиваться раньше. Поэтому мы назначили конец содержащегося события Open текущего события с более высоким приоритетом.

В последнем случае все событие содержится внутри события с более высоким приоритетом и, таким образом, будет отменено вообще. Это исключает и начало, и конец.

Итак, если мы посмотрим на ваш пример, у нас есть S2a Open = 2 и S2a Close = 5. Единственная дата, содержащаяся в этом диапазоне, - S3a Open. Таким образом, мы изменим дату S3a Open к значению S2a Close или 5. Итак, теперь наш результат выглядит следующим образом:

РЕЗУЛЬТАТ:

ID | Action | Priority | Date | 
-------------------------------- 
S2a | Open | 2  | 2 | 
S2a | Close | 2  | 5 | 
S3a | Open | 3  | 5 | 
S3a | Close | 3  | 7 | 
S3b | Open | 3  | 10 | 
S3b | Close | 3  | 11 | 

Это не должно быть трудно экстраполировать от этого как все остальное встает на свои места. (хотя дайте мне знать, если вы хотите получить больше объяснений.)

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

Я не рекомендую мое решение за вас, но вы не просили об эффективности, просто по-другому смотрели на него.

Answer 2

Недавно я написал алгоритм, который делает это. Я сохраняю два массива: один Результат, как ваш, и один массив интервалов S (а не дат, но того, что вы назвали ID). Первоначально массив S сортируется по открытому '(' и Result пуст.

Я также придерживаюсь своего рода списка заказов, но разница с вашей заключается в том, что он не сортируется по приоритету, а по закрытию ')'. Это позволяет быстро удалить интервалы из списка заказов, которые больше не нужно учитывать, потому что они «лежат в прошлом»: вы можете сохранить индекс как все, прежде чем этот индекс будет в прошлом.

Фактическая реализация, однако, не имеет списка индивидуального заказа, но повторно потребляющие S:

S [я] при г> index_1 является входным отсортирован по открытым '('

S [I ] для г < index_1 список порядок сортировки при закрытии «)»

S [я] для «лежат в прошлом» я < index_2

Поэтому, когда запись результатов создается, и мы должны получить следующий S, требуется только диапазон index_1 -> index_2 для поиска (для интервала с наивысшим приоритетом).

позволяет увидеть, если я могу воссоздать первые несколько итераций:

// initialize 
S = [S1a,S2a,S3a,S2b,S1b,S3b,S1c] 
R = [] 
index_1 = 0; 
index_2 = 0; 

// first result starts at smallest open 
R1.start = S1a.open() 
date = S1a.open() // 'current time' 

// check if next entry in S ends the result R1 
S[++index_1] = S2a: S2a.open() < S1a.close and S2a.Priority < S1a.Priority 

// this does not end R1 -> keep S sorted, update index_2 
S[index_1 - 1] = S1a, S[index_1] = S2a, S1a.close < S2a.close // -> OK! no swap needed 
date = S2a.open() 
S[index_2] = S1a: S1a.close() < date // -> OK! no update of index_2 needed 

// check if next entry in S ends the result R1 
S[++index_1] = S3a: S3.open() > S1a.close 

// this ends R1 -> create it, update index_2 
date = S1.close() 
R1.close() = date 
S[index_2] = S1a: S1a.close() = date // -> S1a is 'past' 
index_2++ // update index_2 
S[index_2] = S2a: S2a.close() < date // -> OK! no further update of index_2 needed 

// find the next interval for R2 
search S[i] index_2 <= i < index_1 and pick max priority 
in this case index_2 = 1 and index_1 = 2 so we only need to check one entry (S2a) 

R2.open = max(date, S2a.open()) 

// continue... 

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

Не уверен в производительности, это зависит от типа данных, я думаю (если у вас есть перекрытие между многими интервалами, диапазон index_2 - index_1 большой и поиск этого диапазона, а также сортировка по закрытию ')' каждый раз, когда новый интервал добавляется в список заказов, становится дорогим; если, однако, у вас есть только совпадение между последующими интервалами index_2 - index_1 будет всего лишь 1 элемент, поэтому оба вышеупомянутых действия действительно дешевы)

Это определенно дешевле, если это будет проблемой.

Answer 3

На прошлой неделе я написал еще один алгоритм; с улучшенной наихудшей сложностью. Он имеет очередь приоритетов (я использовал кучу); который изначально пуст. И массив интервалов, отсортированных по дате открытия.

A = [S1a,S2a,S3a,S2b,S1b,S3b,S1c] 
H = [] 

Мы перебираем А (время досрочно); Каждый элемент A будет помещен в очередь в очередь. Так как это приоритетная очередь, корневой элемент H [0] содержит элемент с наивысшим приоритетом. Корневой элемент будет удален после его закрытия.

Вы увидите, что результаты являются корневыми элементами очереди приоритетов с интервалами, соответствующими «времени», в котором этот элемент стал корнем (наивысший приоритет), до момента, когда он был либо выведен из очереди (это закрыт) или «вытолкнут» новым элементом, помещенным в очередь (он был заменен интервалом с более высоким приоритетом перед закрытием).

Более формально:

Когда мы берем следующий элемент в A [я] ++ (авансовый времени); мы сравниваем его с текущим высшим элементом H [0] в очереди приоритетов; и проверьте, есть ли A [i] .Открыть> H [0]. Закройте.

while(A[i].Open > H[0].Close) 
{ 
    if(H[0].Close >= from): 
     We have a new result; R(S = H[0]; Open = from; Closed = H[0].Closed) 
     Set from = H[0].Closed + 1; 
    Dequeue H[0] 
} 

После того, как A [I] .Open < H [0] .close, мы епдиеие А [я] в приоритетной очереди. Могут произойти две вещи;

либо A [i] - это интервал с наивысшим приоритетом и становится новым корнем.Тогда у нас есть новый результат; R (S = старый корень H [0]; Open = from; Closed = A [i] .Открыть); Set from = A [i] .Открыть

Или A [i] «исчезает» в куче, H [0] не изменяется; и мы продолжим.

Как только мы повторили через A; мы продолжаем отменять очередь, создавая при необходимости результаты; пока очередь не будет пустой.

Для памяти вы можете реализовать это, используя один массив, и только делать свопы в этом массиве; первые x индексов представляют собой кучу; а последние у элементов массива А.

Run на вашем примере:

// я = 0: Ставить S1a

A = [S2a,S3a,S2b,S1b,S3b,S1c] 
H = [S1a] 

// я = 1: Ставить S2a

A = [S3a,S2b,S1b,S3b,S1c] 
H = [S1a,S2a] 

// я = 2: первый результат (---- |; Dequeue S1a; Епдиеие S3a

A = [S2b,S1b,S3b,S1c] 
H = [S2a,S3a] 

// i = 3: второй результат | xx |; dequeue S2a (это делает S3a корнем); enqueue S2b; третий результат | oo | (поскольку S2b управляет S3a из положения корня)

A = [S1b,S3b,S1c] 
H = [S2b,S3a] 

// i = 4; enqueue S1b; четвертый результат | xx |

A = [S3b,S1c] 
H = [S1b,S3a,S2b] 

// i = 5; enqueue S3b

A = [S1c] 
H = [S1b,S3a,S2b,S3b] 

// i = 6; пятый результат | ----); dequeue S1b, dequeue S3a, S2b и S3b без создания результатов; enqueue S1c

A = [] 
H = [S1c] 

// шестой результат (-); dequeue S1c; остановить

Answer 4

Бартель алго с использованием очереди приоритета неплох - В Algo разрывы на непересекающихся интервалах, так как:

while(A[i].Open > H[0].Close) 
{ 
    if(H[0].Close >= from): 
     We have a new result; R(S = H[0]; Open = from; Closed = H[0].Closed) 
     Set from = H[0].Closed + 1; 
    Dequeue H[0] 
} 

который случае не перекрывающихся интервалов должно быть на самом деле:

while(A[i].Open > H[0].Close) 
{ 
    if(H[0].Close >= from): 
     We have a new result; R(S = H[0]; Open = from; Closed = H[0].Closed) 
     Set from = A[i].from; 
    Dequeue H[0] 
} 

то есть новый из поступает со следующего интервала