Модуль: Паттерны в динамическом программировании


Задача

5 /7


Ресторан

Теория Нажмите, чтобы прочитать/скрыть


Дисклеймер: способ, описанный ниже, не является универсальным, однако зачастую может решить задачу или помочь прийти к правильному решению.

Если имеется набор промежутков, расположенных на некоторой оси (обычно ось времени или индексы какого-нибудь массива) и необходимо выбрать некоторые из них оптимальным образом, чтобы выбранные промежутки не пересекались, то стоит попробовать применить динамическое программирование.

Примерная схема решения:

Изначально отсортируем имеющиеся промежутки по правой границе. Заведем следующую динамику: dp[i] - ответ для первых i промежутков. 
Пересчитывать будем следующим образом: во-первых, рассмотрим ситуацию, что данный промежуток не будет использоваться, тогда просто dp[i] = dp[i-1]. Заметим, что это обеспечивает неубывание значений dp[i] с ростом i. И это логично, т.к. добавляя новый промежуток, мы не можем ухудшить глобальный ответ: либо мы просто проигнорируем новый промежуток, либо сконструируем более выгодный вариант с помощью него. Теперь, если мы хотим использовать i-й промежуток, то мы можем использовать те промежутки, правые границы которых меньше левой границы текущего промежутка, так как мы должны выбрать набор непересекающихся промежутков. Для этого мы изначально сортировали промежутки по правой границе, чтобы сейчас можно было эффективно найти необходимую позицию. Это можно делать аналитически, если это возможно, но в общем случае можно найти бинпоиском промежуток, правая граница которого меньше левой границы текущего и при этом максимально возможная. Максимизировать правую границу мы хотим из жадных соображений, т.к. с ростом i ответ может только увеличиваться. Соответственно, находим необходимую позицию p и пересчитываем dp[i] через dp[p] и i-й промежуток.

Задача

Ресторан получил n заказов на проведение банкета. Каждый заказ характеризуется двумя величинами: моментом начала банкета li и моментом конца ri (li ≤ ri).

Руководство ресторана может либо принять заказ, либо отвергнуть его. Какое наибольшее количество заказов может быть принято?

Никакие два принятых заказа не могут пересекаться, то есть не должно существовать момента времени, который принадлежит сразу двум принятым заказам. Если один из заказов начинается в момент, когда заканчивается другой, то они не могут быть приняты вместе.

Входные данные:
В первой строке находится целое число n (1 ≤ n ≤ 200000) — количество заказов. В каждой из следующих n строк находится пара целых чисел li, ri (0 ≤ li ≤ ri ≤ 109).

Выходные данные:
Выведите наибольшее количество заказов, которые могут быть приняты.

Примеры:
 
Входные данные Выходные данные
2
7 11
4 7
1
5
1 2
2 3
3 4
4 5
5 6
3
6
4 8
1 5
4 7
2 5
1 3
6 8
2

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Комментарий учителя