Каждая смена сотрудника — отрезок времени [start, end], включая границы. Охранник хочет обойти посты как можно меньше раз, но так, чтобы во время каждой смены был хотя бы один обход. Функция min_checks(shifts) жадно выбирает моменты обходов и возвращает их список. В ней две ошибки — найдите и исправьте их.
min_checks([(1, 4), (2, 6), (5, 8), (7, 9)]) # [4, 8] — 2 обхода
min_checks([(1, 3), (3, 5)]) # [3] — один обход в момент 3 годится обеим сменамЗаготовка задачи обновилась с тех пор, как вы сохранили свой код.
Сбросить редактор к заготовке? Ваш код будет удалён.
def min_checks(shifts: list[tuple[int, int]]) -> list[int]:
"""Минимальный набор моментов, чтобы в каждую смену был хотя бы один обход."""
checks: list[int] = []
for start, end in sorted(shifts, key=lambda s: s[0]):
if not checks or checks[-1] <= start:
checks.append(end) # как можно позже, но в пределах этой смены
return checksВывод обрезан: показаны первые строки.
def _check(shifts, optimum):
got = min_checks(shifts)
assert isinstance(got, list), f"ожидался список моментов, получено {got!r}"
for start, end in shifts:
assert any(start <= t <= end for t in got), f"в смену [{start}, {end}] не было обхода: {got}"
assert len(got) == optimum, f"обходов {len(got)}, а можно обойтись {optimum}: {got}"
def test_example():
"""Пример: 2 обхода"""
_check([(1, 4), (2, 6), (5, 8), (7, 9)], 2)
def test_touching_shifts():
"""Смены касаются границами — хватает одного обхода"""
_check([(1, 3), (3, 5)], 1)
def test_nested_shift():
"""Короткая смена внутри длинной"""
_check([(1, 10), (2, 3)], 1)
def test_empty():
"""Смен нет → []"""
got = min_checks([])
assert got == [], f"ожидалось [], получено {got!r}"
def test_disjoint():
"""Непересекающиеся смены — по обходу на каждую"""
_check([(1, 2), (4, 5), (7, 8)], 3)
def test_point_shifts():
"""Смены длиной в один момент"""
_check([(5, 5), (5, 5), (6, 6)], 2)
def test_bigger():
"""40 смен в перемешанном порядке — хватает 12 обходов"""
shifts = [((i * 37) % 50, (i * 37) % 50 + (i % 7) + 1) for i in range(40)]
_check(shifts, 12)Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 guard_checks.py — тесты те же, результат покажет ✓ / ✗ и итог.
Запустите тесты: в одних случаях смена остаётся без обхода, в других обходов больше, чем нужно. Это разные ошибки.
Жадное правило: ставим проверку как можно позже, но так, чтобы успеть в ту смену, которая заканчивается раньше всех. По какому полю тогда нужно сортировать?
Смена [start, end] включает обе границы. Засчитывается ли ей проверка ровно в момент start?
def min_checks(shifts: list[tuple[int, int]]) -> list[int]:
"""Минимальный набор моментов, чтобы в каждую смену был хотя бы один обход."""
checks: list[int] = []
for start, end in sorted(shifts, key=lambda s: s[1]):
if not checks or checks[-1] < start:
checks.append(end) # как можно позже, но в пределах этой смены
return checks