Финальный проект: планировщик, маршруты и защита выбора

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

Вход и результат

Работа содержит уникальный строковый ID, название и неотрицательную длительность. Зависимость before→after означает: before должен завершиться прежде, чем можно начать after. В отчёте должны быть все работы ровно один раз, порядок зависимостей и понятная ошибка при неизвестном ID, повторе ID или цикле.

Выберите небольшой JSON-формат и опишите его в README. Например:

{
  "jobs": [
    {"id":"fetch","name":"Получить исходники","minutes":2},
    {"id":"generate","name":"Сгенерировать код","minutes":3},
    {"id":"build","name":"Собрать приложение","minutes":5},
    {"id":"docs","name":"Подготовить документацию","minutes":4}
  ],
  "edges": [["fetch","generate"],["generate","build"]]
}

Работа docs независима. Допустимы разные топологические порядки, но build должен идти после generate, а generate после fetch. Не добавляйте зависимости только для получения любимого внешнего вида отчёта.

Архитектура решения

При загрузке сформируйте map ID→индекс и обратный массив. Проверяйте повтор ID до перезаписи map. Затем преобразуйте связи в список смежности. Пользовательские строки не должны попадать в доступ по индексу без проверки.

Разделите чтение JSON, валидацию, чистые алгоритмы и вывод. Ошибка JSON и цикл графа — разные причины отказа. Чистые функции удобнее тестировать на маленьких структурах, чем каждый раз запускать всю команду. CLI остаётся тонким слоем вокруг них.

Используйте алгоритм Кана или DFS для порядка зависимостей. Если нужен воспроизводимый минимальный доступный ID, сравнивайте строковые ID в куче; их сравнение зависит от длины, поэтому оценка не должна молча считать любой текст бесплатным.

Три режима работы

Первый режим plan возвращает порядок. Второй path A B ищет минимальное число переходов между работами по направленным зависимостям через BFS. Такой путь показывает цепочку зависимости, а не длительность проекта. Третий режим top K выбирает K самых длительных работ и явно задаёт порядок при равенстве.

В top допускаются одинаковые длительности, но ID различны. Если используете TopK только на числах, затем нельзя восстановить работы через map duration→job: равные значения затрут друг друга. Сохраняйте записи с ID в куче и задайте компаратор.

Расширение после базового завершения

Добавьте расчёт минимального времени завершения всего проекта при неограниченном числе исполнителей. В DAG earliestFinish[v] равен duration[v] плюс максимальный earliestFinish среди предшественников, а для вершин без предшественников — duration[v]. Вычисляйте в топологическом порядке.

Для примера цепочка fetch→generate→build занимает 10 минут, независимая docs —4; весь проект завершится за 10. Это длина критического пути в модели, а не сумма всех 14 минут. При одном исполнителе длительность 14; при двух и ограничениях ресурсов задача уже меняется. Не объявляйте найденное число расписанием для любого числа работников.

План независимой проверки

Сначала создайте тесты: пустой проект, одна работа, две независимые, цепочка, ромб, цикл, петля, неизвестный ID, повтор ID, одинаковые длительности. Для plan проверяйте перестановку всех ID и каждое ребро. Для path — начало, конец, рёбра и минимальную длину. Для top — количество, выбранные приоритеты и отсутствие потерь при равенстве.

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

На проект заложите 4–8 часов. Все инструменты локальные, Go и стандартная библиотека; обязательных платных сервисов нет. Заготовки и открытые эталоны находятся в лабораториях. Эталон алгоритма не является готовым финальным CLI: объединение и договоры должны быть вашим решением.

Критерии готовности и защита

Проект собирается по одной инструкции, тесты проходят, неверный вход выдаёт объяснимую ошибку. В README записаны модель направления, правила равенства, оценки времени и памяти по V,E,K, различие маршрута и критического пути. Код не меняет вход без заявленного договора.

На защите измените условия: работы начали появляться во время выполнения. Объясните, что прежний статический порядок описывает старый снимок графа, а вставка зависимости может сделать уже выполненное расписание недопустимым. Затем предложите договор обновления. Второе изменение — платная стоимость работ: задача «больше встреч» из предыдущей главы больше не оптимизирует доход автоматически.

Разбор типичных ошибок

Сортировка ID не заменяет топологию. Один ожидаемый порядок не годится как универсальный тест. DSU не находит направленный цикл. BFS не минимизирует длительность. Успешные тесты на цепочке не проверяют общую вершину-потомок. Эти ошибки обнаруживаются небольшими контрпримерами, а не только большой случайной нагрузкой.

После проекта повторите слабые темы, попробовав новое условие без подсказки. Дополнительное углубление дают MIT 6.006 и Princeton Algorithms: математические предпосылки и языки примеров у них отличаются от этого курса.