Последовательности пакетов, которые охватывают время таким образом, чтобы перекрытие между последовательностями в пакете было максимальным
У меня есть набор данных, состоящий из идентификационных номеров и отметок времени. Каждый идентификатор существует в одном непрерывном подмножестве диапазона временных отметок.
Вот пример визуализации структуры данных.
Теперь мне нужно объединить эти идентификаторы в группы из n таким образом, чтобы продолжительность жизни идентификаторов в каждой группе перекрывалась в максимально возможной степени.
Эта визуализация выше не иллюстрирует истинное содержание моего набора данных - есть 1813 временных меток и 1424 IDS, из которых 590 охватывают все 1813 временных меток. Другие 834 имеют большой разброс продолжительности жизни, некоторые из них охватывают более 1700 временных отметок, а пара охватывает только две временные отметки.
Будем благодарны за любые идеи о простых способах достижения этого.
РЕДАКТИРОВАТЬ
Другим важным аспектом, который я не упомянул, является то, что каждая партия из n идентификаторов может быть обрезана по длине диапазона продолжительности жизни в этой партии. Таким образом, я полагаю, что целью проблемы является пакетирование последовательностей таким образом, чтобы доля красных квадратов в пакете была минимизирована.
Другими словами, если бы я выполнял дозирование в группах по 3 человека и взял на своих изображениях идентификаторы 117, 118 и 119, то доля красных квадратов будет 14/30.