Всем привет. Мягко говоря, давно ничего не писал. Попробуем нарушить эту традицию )
Сегодня рассмотрим следующую интересную задачу.
Имеется некий список отрезков в одномерном пространстве. Каждый отрезок задан парой координат его левой и правой точек. Задача - найти минимальное количество линий, на которых можно разместить все эти отрезки таким образом, чтобы они не пересекались друг с другом.
В общем случае задача сводится к умному перебору. Для разнообразия рассмотрим такую
категорию алгоритмов, как эвристические. Эти алгоритмы не гарантируют нахождение самого лучшего решения (хотя это и не исключено), но почти всегда дают вполне приемлемые результаты при сравнительно небольших временных затратах (этот показатель можно регулировать).
Давайте рассмотрим такой алгоритм. Будем действовать максимально просто.
Сегодня рассмотрим следующую интересную задачу.
Имеется некий список отрезков в одномерном пространстве. Каждый отрезок задан парой координат его левой и правой точек. Задача - найти минимальное количество линий, на которых можно разместить все эти отрезки таким образом, чтобы они не пересекались друг с другом.
В общем случае задача сводится к умному перебору. Для разнообразия рассмотрим такую
категорию алгоритмов, как эвристические. Эти алгоритмы не гарантируют нахождение самого лучшего решения (хотя это и не исключено), но почти всегда дают вполне приемлемые результаты при сравнительно небольших временных затратах (этот показатель можно регулировать).
Давайте рассмотрим такой алгоритм. Будем действовать максимально просто.
