Мне было интересно, существует ли существующая проблема в литературе, которая похожа на следующую:
Предположим, в реальном времени потоковая передача сигналов. Каждый сигнал имеет Время прибытия, длительность и номер приоритета.
Два сигнала сталкиваются, если они перекрываются в какой-то момент времени.
Я хочу взять на вход количество X источников (каждый источник посылает мне сигналы в режиме реального времени), и иметь возможность планировать сигналы и отправлять их в очередь Y на выходе.
Каждая очередь на выходе будет получать поток неперекрывающихся сигналов.
Ограничение состоит в том, что я не хочу сбрасывать сигналы с приоритетом j, в то время как другой перекрывающийся сигнал с приоритетом k
Теперь, с определенным количеством сигналов на входе, можно искать локальные максимумы, которые должны быть отправлены, и искать совместимые сигналы на основе приоритета. Но при потоковой передаче в реальном времени может быть случай, когда вы получаете сигналы с возрастающим приоритетом в течение длительного времени, поэтому для локальных максимумов может потребоваться много времени. Чтобы получить быстрый ответ, я подумал о том, чтобы разделить поток на основе временного окна или окна #signals, а затем проанализировать его, допуская небольшой процент ошибок по отношению к оптимальному решению.
Есть ли какие-либо проблемы в литературе, возможно, учитывая компромисс между окном и процентом ошибочных сигналов?
Небольшой пример:
----(1)
..-----(2)
.....-------(5)
......----(3)
При наличии 2 очередей результат будет:
1) 5
2) 1 3
Наихудший сценарий выглядит следующим образом:
----1
..-----2
...------3
.....------4
.......-----5
........------6
.........----------7
и т. Д., Где приоритет всегда увеличивается, и вы никогда не сможете выбрать сигнал, который не сталкивается с другими сигналами с более высоким приоритетом, и начать анализ в обратном направлении, чтобы найти совместимые сигналы, которые можно отправить.