Блог пользователя chugaev

Автор chugaev, 5 лет назад, По-русски

Столкнулся со следующей задачей.
Есть N отрезков, для каждого отрезка известны координаты начала и конца. Также имеется неограниченное количество контейнеров. Отрезки можно разместить в одном контейнере, если они не пересекаются, при этом двигать отрезки нельзя. Необходимо минимизировать количество контейнеров. Помогите найти оптимальный алгоритм решения.

Данные для задачи:

Первое число N — количество отрезков(1 <= N <= 1000), далее N пар чисел — координата начала и координата конца каждого отрезка. В качестве ответа — количество контейнеров и для каждого контейнера номера отрезков которые попали в этот контейнер. Пример:

Ввод:

5
1 5
2 3
6 8
4 7
9 10

Вывод:

2 - количество контейнеров
2 4 5 - номера отрезков в первом контейнере
1 3 - номера отрезков во втором контейнере

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится