print2087. Запасы на зиму

printЗапасы на зиму

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Всем известно, что вампиры пьют кровь. Большинство вампиров пьют кровь людей, но Эдвард не такой. Он не хочет убивать людей, поэтому он пьeт только кровь животных и ту, которую люди сдают в пункты сдачи крови. Но скоро зима, животных будет не найти, а все пункты сдачи крови закроются. Поэтому Эдвард решил запастись кровью на зиму.
Эдвард знает `n` пунктов, в которых он сможет достать кровь. Одна проблема – пункты работают только в определeнные моменты времени. Пункт номер `i` работает только с `l_i` минуты по `r_i`. Эдвард получит кровь в этом пункте только в том случае, если пробудет в нeм всe время работы, то есть в минуты с номерами с `l_i` по `r_i`.
Эдвард хочет достать как можно больше крови, чтобы зимой у него не было проблем. Для этого ему надо посетить некоторые пункты сдачи крови. Понятно, что он не может оказаться в двух местах в один и тот же момент времени, поэтому все пункты ему не всегда удастся посетить, но ему бы хотелось посетить как можно больше. Эдвард – вампир, поэтому он перемещается очень быстро, можно считать, что между пунктами сдачи крови он перемещается мгновенно. Помогите ему – скажите, какое максимальное количество пунктов сдачи крови ему удастся посетить.
Во всех пунктах Эдвард получает одинаковое количество крови.
В первой строке входного файла дано число `n` (`1\ ≤\ n\ ≤\ 10^5`) – количество пунктов сдачи крови. В каждой из следующих `n` строк записано два числа `l_i` и `r_i` (`1\ ≤\ l_i\ <\ r_i\ ≤\ 10^9`) – моменты времени, в которые работает пункт сдачи крови номер `i`.
В первой строке выходного файла выведите максимальное количество пунктов сдачи крови, которые сможет посетить Эдвард. Во второй строке выведите номера этих пунктов. Номера выводите в том порядке, в котором Эдвард будет их посещать. Пункты нумеруются с 1 в порядке, в котором они заданы во входном файле.
Если ответов несколько, разрешается вывести любой.

Пример ввода 1

2
1 2
3 4

Пример вывода 1

2
1 2

Пример ввода 2

4
1 4
2 5
3 6
4 7

Пример вывода 2

2
1 4
В первом тестовом примере Эдварду ничего не мешает сначала посетить первый пункт сдачи крови, а затем второй.
Во втором примере он может сначала побывать в первом пункте в моменты времени с 1 до 4 и сразу же, в момент времени 4, оказаться в четвертом пункте.
Источник: neerc.ifmo.ru/school
loading