Суть Чтение реальных greedy-фрагментов: interval-планировщик с неверным ключом сортировки, greedy, проигрывающий DP, и проход Gas Station. Предскажите поведение и выберите фикс с наибольшим рычагом.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на senior-высоте — в орбите
◷ 14 min
Баги greedy тихие: код выполняется, возвращает что-то правдоподобное и ошибается только на тех входах, которые вы не протестировали. Читайте каждый фрагмент как на ревью — найдите выбор, который не является доказуемо безопасным, и выберите фикс, который senior-инженер делает первым.
Цель
Отработайте цикл, который вы запускаете на каждом greedy: прочитать локальный выбор, решить, доказуемо ли он оптимален, и потянуться к правильному ключу сортировки, правильному инварианту или к DP — прежде чем доверять результату.
Фрагмент 1 — interval-планировщик
// Цель: выбрать МАКСИМУМ непересекающихся интервалов.function maxNonOverlapping(intervals) { const sorted = [...intervals].sort((a, b) => a[0] - b[0]); // сортировка по СТАРТУ let count = 0, lastEnd = -Infinity; for (const [start, end] of sorted) { if (start >= lastEnd) { count++; lastEnd = end; } } return count;}// maxNonOverlapping([[1, 10], [2, 3], [4, 5]]) -> ?
Викторина
Completed
Что вернётся на [[1,10], [2,3], [4,5]] и каков фикс в одну строку?
Heads-up Сортировка по старту берёт длинный [1,10] первым и затем блокируется от обоих коротких интервалов, возвращая 1, а не 2. Сортировка по старту — это ключ для MERGING интервалов, а не для максимизации.
Heads-up [1,10] пересекается и с [2,3], и с [4,5], поэтому их нельзя выбрать все. С сортировкой по старту берётся только [1,10], возвращая 1.
Heads-up Удаление сортировки делает его неверным, а не быстрее — greedy зависит от порядка. Дефект в КЛЮЧЕ (старт против финиша), а алгоритм уже O(n log n).
Фрагмент 2 — greedy, проигрывающий DP
// «Минимум монет для amount», всегда беря самую крупную подходящую монету.function greedyCoins(coins, amount) { const sorted = [...coins].sort((a, b) => b - a); let left = amount, count = 0; for (const c of sorted) { while (left >= c) { left -= c; count++; } } return left === 0 ? count : Infinity;}// greedyCoins([1, 5, 6, 9], 11) -> ? (DP-оптимум равен 2: 5 + 6)
Heads-up Возрастающий порядок заставил бы greedy брать множество единиц — ещё хуже. Провал внутренне присущ набору номиналов, а не направлению сортировки. Фикс — DP.
Heads-up 5 + 6 = 11 использует ровно 2 монеты, обыгрывая greedy с тремя. DP минимизирует исчерпывающе и корректен; greedy возвращает худший ответ.
Heads-up Проверка лишь сообщает о невыполнимости; к оптимальности она отношения не имеет. Даже с чистой проверкой greedy всё равно возвращает 3 для этого набора номиналов. Только DP гарантирует минимум.
Фрагмент 3 — проход Gas Station
function canCompleteCircuit(gas, cost) { let total = 0, tank = 0, start = 0; for (let i = 0; i < gas.length; i++) { const diff = gas[i] - cost[i]; total += diff; tank += diff; if (tank < 0) { start = i + 1; tank = 0; } } return total >= 0 ? start : -1;}
Викторина
Completed
Ревьюер хочет удалить переменную total и возвращать start напрямую, аргументируя, что сброс и так находит ответ. Почему total должен остаться?
Heads-up Уберите total — и функция может вернуть фиктивный старт на невыполнимых входах (например, при отрицательном суммарном net fuel), где она обязана вернуть -1. total — несущая проверка выполнимости, а не отладочный вывод.
Heads-up Бак сбрасывается строкой tank = 0 внутри if, независимо от total. total не участвует в сбросах — его единственная задача в финальном вердикте о выполнимости.
Heads-up Они разные: tank — net fuel с текущего кандидата-старта (решает о сбросах), total — net fuel по всему кругу (решает о выполнимости). Слияние ломает обе роли.
Фрагмент 4 — граница цикла Jump Game II
function jump(nums) { let jumps = 0, curEnd = 0, farthest = 0; for (let i = 0; i < nums.length; i++) { // цикл до n-1 farthest = Math.max(farthest, i + nums[i]); if (i === curEnd) { jumps++; curEnd = farthest; } } return jumps;}// jump([2, 3, 1, 1, 4]) -> ? (истинный минимум равен 2)
Викторина
Completed
Это возвращает 3 на [2,3,1,1,4], но минимум равен 2. В чём ошибка на единицу и каков фикс?
Heads-up Старт с 1 пересчитал бы с первого прыжка и сломал случай [0] длины 1 (которому нужно 0 прыжков). Настоящий баг — граница цикла, она должна останавливаться на n-2.
Heads-up Фронтир (самый дальний достижимый) только растёт — Math.max корректен. Min схлопнул бы его и отрапортовал недостижимость. Дефект в границе цикла.
Heads-up 0 -> 1 -> 4 достигает конца за 2 прыжка. Цикл до n-1 тратит лишний третий прыжок на сам индекс цели; остановка на n-2 это чинит.
Итог
Каждый greedy читается одинаково: назовите локальный выбор, затем спросите, доказуемо ли он безопасен. Фрагмент 1 использовал неверный ключ сортировки (старт вместо финиша) для максимизации; фрагмент 2 применил greedy на наборе номиналов без greedy choice property, где корректен только DP; фрагмент 3 показал, что глобальный инвариант выполнимости (total >= 0) несущий и отделён от локального сброса; фрагмент 4 был классической ошибкой на единицу в Jump Game II (цикл до n-2, никогда не прыгать из цели). Диагностируйте небезопасный выбор, затем чините ключ, инвариант или откатывайтесь к DP.