0062. Где поставить радар?

Имя входного файла:	radar.in
Имя выходного файла:	radar.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

На супертрассе работает группа инспекторов дорожно-патрульной службы. Чтобы не творилось беспредела, за каждым инспектором был официально закреплен определенный участок дороги, выход за территорию которого приравнивался к увольнению. Участки инспекторов могли пересекаться и даже совпадать, что не мешало им радоваться немалым доходам и щедро делиться ими с товарищем начальником. Стремясь повысить свое благосостояние и порядок на вверенной ему дороге, товарищ начальник набирал дополнительных сотрудников и отводил им новые участки.

Беда пришла, когда ее не ждали… После того, как несколько инспекторов разместились поблизости, возник скандал: автомобиль после первой остановки не успевал набрать запрещенную скорость и все доходы достались только одному… Безвинно пострадавший товарищ начальник потребовал, чтобы каждый инспектор размещал свой радар вблизи закрепленного за ним собственного километрового столба.

Помогите товарищу начальнику, который, как известно, университетов не кончал, решить непростую задачу поиска наибольшего множества (желательно – всех) инспекторов, каждому из которых удастся выделить по персональному километровому столбу в границах отведенных им участков.

Формат входного файла

Первая строка данных задачи – два целых числа: 1≤ n≤ 1000 – количество инспекторов и 0≤ S≤ 10000 – длина дороги. Последующие n строк содержат по два целых числа 0≤ a_j≤ b_j ≤ S – границы контрольного участка инспектора 1≤ j≤ n.

Формат выходного файла

Ответом является искомое наибольшее количество инспекторов.

Пример:

radar.in	radar.out
4 6 2 2 3 6 1 2 1 1	3

Источник: Petrozavodsk Winter 2003. Take-Off, Monday, February 03

Обсудить       Отправить решение



Версия для печати