Сначала программа открывает файл
26.txt и считывает количество заявок n. Далее создаётся пустой список zayavki, в который будут записываться все заявки на уборку.Каждая заявка во входном файле задаётся двумя числами: началом участка и его длиной. В цикле программа считывает эти данные и сразу переводит их в более удобный формат: вместо начала и длины сохраняет конец участка и начало участка:
zayavki.append([start + len_uchastka, start])
Это делается для того, чтобы потом отсортировать заявки по моменту окончания участка. Такой приём удобен в задачах, где нужно выбрать максимальное количество непересекающихся отрезков.
После этого список заявок сортируется:
zayavki.sort()
Так как первым элементом каждой заявки записан конец участка, сортировка происходит именно по концу участка. То есть раньше будут рассматриваться те заявки, которые заканчиваются раньше.
Затем создаётся список
uborka, куда будут попадать выбранные участки. Сначала туда добавляется конец самого первого участка после сортировки:
uborka = [zayavki[0][0]]
Дальше программа перебирает все заявки. Для каждой заявки проверяется условие:
if start >= uborka[-1]:
Оно означает: если начало текущего участка не меньше конца последнего выбранного участка, то эти участки не пересекаются. Значит, такую заявку можно выполнить, и конец этого участка добавляется в список
uborka.Таким образом, программа жадно выбирает заявки: каждый раз берёт подходящий участок, который заканчивается как можно раньше. Это позволяет получить максимальное количество заявок.
Отдельно внутри цикла есть проверка:
if start >= 9531:
print(10000 - end)
Она нужна для второй части задачи — найти минимальную длину неубранного участка в конце дороги. Программа смотрит на подходящие последние заявки, которые могут быть взяты в конце, и выводит длину оставшегося хвоста дороги:
10000 - end
То есть если последний выбранный участок заканчивается в точке
end, то неубранным в конце остаётся участок от end до 10000.В самом конце программа выводит:
print(len(uborka))
Это количество выбранных заявок, то есть максимальное количество заявок, которые можно выполнить без пересечений.
➡️Итоговая идея программы такая: сначала все заявки переводятся в отрезки и сортируются по правому концу, затем жадным алгоритмом выбирается максимальное количество непересекающихся участков, а дополнительно проверяется, какой вариант позволяет оставить минимальный неубранный участок в конце дороги.
Надеюсь, многие справились!🧘