На этот раз ваша задача — собрать подписи со всех жильцов дома. Вам известно время, в которое каждый из них будет у себя. Естественно, вам хочется собрать все подписи, заходя в дом минимальное количество раз. Для простоты давайте предположим, что вы, зайдя в дом, собираете подписи сразу со всех жильцов, которые на месте.
В дальнейшем под сегментом будем понимать интервал времени нахождения жильца в доме. Количество жильцов будет соответствовать количеству сегментов.
- Входные данные: Количество сегментов в первой строке — $n$. Каждая из следующих $n$ строк содержит два целых числа $l_i$ и $r_i$ (разделены пробелом), которые указывают на координаты границ $i$-го сегмента.
- Выходные данные: Минимальное количество $k$ точек на первой строке и координаты $k$ точек целыми числами (разделены пробелом) на второй строке. Выводить точки можно в любом порядке. При наличии нескольких наборов точек, можно вывести любой из них.
- Ограничения: $1 \le n \le 100$; $0 \le l_i \le r_i \le 10^9$ для всех $i$.
Пример 1
Ввод | Вывод |
---|---|
3 1 3 2 5 3 6 | 1 3 |
Все три сегмента $[1,3]$, $[2,5]$, $[3,6]$ содержат точку с координатами 3.
Пример 2
Ввод | Вывод |
---|---|
4 4 7 1 3 2 5 5 6 | 2 3 6 |
Второй и третий сегменты содержат точку с координатами $3$, в то время как первый и четвертый содержат точку с координатами $6$. Одной точкой покрыть все сегменты нельзя, так как $[1,3]$ и $[5,6]$ не пересекаются. В этом случае есть еще одно верное решение — точки 2 и 5.
Решение
Решение заключается в выявлении сегмента с наименьшим значением правой границы.
Самое маленькое значение границы сегмента: $r_m=\min{r_1, \dotsc, r_n}$. Мы утверждаем, что существует оптимальное решение, включающее в себя точку $r_m$. Чтобы доказать это, возьмём оптимальное решение $S$. Оно должно покрывать сегмент $[l_m,r_m]$, поэтому $S$ содержит точку $x$, что приводит к $l_m \le x \le r_m$. Если $x=r_m$, то наша работа закончена. Иначе $x \lt r_m$. В этом случае мы можем заменить $x$ на $r_m$ в $S$.
Понятно, что это не меняет размер решения $S$. Чтобы доказать, что $S$ всё ещё является решением, подойдём от противного и предположим, что некий сегмент $[l_i,r_i]$ покрывается $x$, но не покрывается $r_m$. Это означает $l_i \le x \le r_i < r_m$ и противоречит тому, что $r_m$ — самое маленькое значение правой границы.
Таким образом, мы приходим к следующему алгоритму:
- добавить в решение минимальное значение правой границы $r_m$,
- отбросить все сегменты, покрытые $r_m$,
- повторить.
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
На рисунке ниже показан пример.
Время выполнения составит $O(n^2)$, где $n=|segments|$, так как используется не более $n$ итераций цикла while (при каждой итерации отбрасывается как минимум один сегмент), и каждая итерация сводится к проверке списка $segments$ (одним сканированием находится значение $r$, а другим убираются сегменты, покрываемые $r$).
Этот алгоритм уже достаточно быстрый, чтобы успешно пройти оценку. Однако можно дополнительно сократить время выполнения с $O(n^2)$ до $O(n\log n)$, если отсортировать сегменты от малых до больших значений правой границы и затем просто просканировать список один раз.