6.4. Задача «Сбор подписей»

На этот раз ваша задача — собрать подписи со всех жильцов дома. Вам известно время, в которое каждый из них будет у себя. Естественно, вам хочется собрать все подписи, заходя в дом минимальное количество раз. Для простоты давайте предположим, что вы, зайдя в дом, собираете подписи сразу со всех жильцов, которые на месте.

В дальнейшем под сегментом будем понимать интервал времени нахождения жильца в доме. Количество жильцов будет соответствовать количеству сегментов.

• Входные данные: Количество сегментов в первой строке — . Каждая из следующих строк содержит два целых числа и (разделены пробелом), которые указывают на координаты границ -го сегмента.
• Выходные данные: Минимальное количество точек на первой строке и координаты точек целыми числами (разделены пробелом) на второй строке. Выводить точки можно в любом порядке. При наличии нескольких наборов точек, можно вывести любой из них.
• Ограничения: ; для всех .

Пример 1

Ввод	Вывод
3 1 3 2 5 3 6	1 3

Все три сегмента , , содержат точку с координатами 3.

Пример 2

Ввод	Вывод
4 4 7 1 3 2 5 5 6	2 3 6

Второй и третий сегменты содержат точку с координатами , в то время как первый и четвертый содержат точку с координатами . Одной точкой покрыть все сегменты нельзя, так как и не пересекаются. В этом случае есть еще одно верное решение — точки 2 и 5.

Решение

Решение заключается в выявлении сегмента с наименьшим значением правой границы.

Самое маленькое значение границы сегмента: . Мы утверждаем, что существует оптимальное решение, включающее в себя точку . Чтобы доказать это, возьмём оптимальное решение . Оно должно покрывать сегмент , поэтому содержит точку , что приводит к . Если , то наша работа закончена. Иначе . В этом случае мы можем заменить на в .

Понятно, что это не меняет размер решения . Чтобы доказать, что всё ещё является решением, подойдём от противного и предположим, что некий сегмент покрывается , но не покрывается . Это означает и противоречит тому, что — самое маленькое значение правой границы.

Таким образом, мы приходим к следующему алгоритму:

• добавить в решение минимальное значение правой границы ,
• отбросить все сегменты, покрытые ,
• повторить.

SegmentsCover(segments):
    points←empty set
    while segments is not empty:
        r_m = minimum right endpoint of a segment from segments
        add r_m points
        remove segments covered by r_m from the set segments
    return points

На рисунке ниже показан пример.

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

Этот алгоритм уже достаточно быстрый, чтобы успешно пройти оценку. Однако можно дополнительно сократить время выполнения с до , если отсортировать сегменты от малых до больших значений правой границы и затем просто просканировать список один раз.