Подкажите алгоритм для определения минимального покрывающего диапазона?

Доброго времени суток!
Дано: у меня есть диапазоны данных (параметры), в формате «Стартовый байт» — «Стартовый бит» — «Количество бит». Их может быть несколько, они могут пересекаться, они не обязательно идут по порядку возрастания стартового байта. Мне нужно осуществить запрос в формате «Стартовый байт» — «Количество байт», который бы покрывал все диапазоны бит (может быть несколько участков).
Необходимо соответственно придумать алгоритм кодирования и декордирования, который бы сохранял (или позволял восстановить) порядок параметров.
И несколько примеров:
1) 0-0-5, 0-5-4, 10-3-3 — общие диапазоны будет 0-2 и 10-1.
2) 0-0-1, 0-1-15, 0-0-1, 0-1-15 — общий диапазон 0-4.
3) 94-0-1, 104-0-5, 92-0-2, 94-1-1 — общий диапазон 94-1, 104-1, 92-1.

Вот мне надо как-то это унифицировать, и объединить под общую гребенку, ничего не подскажете?
  • Вопрос задан
  • 2492 просмотра
Решения вопроса 1
@MikhailEdoshin
Сложить в кучу по номеру стартового байта (наименьший — верхний), вынуть первый элемент, сделать на его основе элемент в финальном формате — это будет текущий элемент. Затем в цикле брать следующий элемент, из кучи, смотреть, пересекается ли он с текущим. Если да, модифицировать текущий, если нет — передать текущий в финальный список (раз это куча, других пересекающихся элементов точно нет), и сделать новый текущий элемент.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы