Подходит ли платформа для начинающих без опыта работы?

Да, курсы разбиты по уровням: Junior, Middle, Senior. Начинающие могут стартовать с базовых тем Python, Docker и алгоритмов и постепенно двигаться к более сложным темам.

Как быстро можно подготовиться к собеседованию на позицию Junior разработчика?

При занятиях 1–2 часа в день — от 2 до 4 недель на основные темы. Платформа анализирует слабые места по результатам квизов и строит персональный план подготовки.

Какие технологии охватывает платформа?

Python, FastAPI, Django, Docker, алгоритмы и структуры данных, Agile/Scrum, SQL, CI/CD, системный дизайн, код-ревью и более 50 других тем для разработчиков.

Платформа бесплатная?

Большинство учебных материалов и квизов доступны бесплатно после регистрации. Регистрация занимает менее минуты.

Как платформа помогает найти работу программистом?

Платформа даёт фундаментальные знания, которые проверяют на технических собеседованиях: алгоритмы, архитектура, фреймворки. Мок-интервью имитирует реальное собеседование. Система прогресса показывает, какие темы нужно подтянуть перед собеседованием.

greedy

Greedy Algorithms

Жадные алгоритмы с доказательствами. Интервальные задачи, выбор оптимального.

Greedy Algorithms

Жадные алгоритмы делают локально оптимальный выбор на каждом шаге. Требуют доказательства корректности.

1. Суть паттерна

Greedy Algorithm (Жадный алгоритм) — это алгоритм, который на каждом шаге делает локально оптимальный выбор в надежде, что это приведёт к глобально оптимальному решению.

1.1 Термины

Ассоциативность — свойство операции, при котором результат не зависит от расстановки скобок.

Коммутативность — свойство операции, при котором результат не зависит от порядка операндов.

Монотонная функция — функция, которая только возрастает или только убывает.

Простое число — натуральное число больше 1, которое делится только на 1 и на само себя.

НОД (Наибольший общий делитель) — наибольшее число, на которое делятся оба данных числа.

НОК (Наименьшее общее кратное) — наименьшее число, которое делится на оба данных числа.

Когда применять

✅ Оптимальная подструктура — оптимальное решение содержит оптимальные решения подзадач
✅ Жадный выбор — локально оптимальный выбор ведёт к глобально оптимуму
✅ Интервальные задачи — выбор интервалов с earliest finish time
✅ Минимизация/максимизация — найти минимальное/максимальное значение
✅ Доказуемая корректность — можно доказать, что жадность работает

Предусловия

Доказательство корректности — нужно доказать, что жадный выбор оптимален
Отсутствие будущих зависимостей — текущий выбор не зависит от будущих
Монотонность — каждый шаг приближает к цели

Как доказать корректность

Proof by contradiction — предположить, что есть лучшее решение, прийти к противоречию
Exchange argument — показать, что жадное решение не хуже любого другого
Induction — доказать по индукции для всех шагов

Сравнение с альтернативами

Задача	Greedy	Dynamic Programming	Brute Force
Interval Scheduling	✅ O(n log n)	⚠️ O(n²)	❌ O(2^n)
Coin Change (US coins)	✅ O(n)	⚠️ O(n × amount)	❌ O(2^n)
Knapsack (fractional)	✅ O(n log n)	❌ Не применимо	❌ O(2^n)
Knapsack (0/1)	❌ Не работает	✅ O(n × W)	❌ O(2^n)

Вывод: Greedy быстрее DP, но работает не для всех задач. Всегда проверяйте на контрпримерах!

Типичные жадные стратегии

# Interval Scheduling: сортировать по окончанию
intervals.sort(key=lambda x: x[1])

# Coin Change (жадный): брать наибольшие номиналы
coins.sort(reverse=True)

# Maximum Subarray: max(num, current + num)
current = max(num, current + num)

2. Шаблон

# Общая структура
def greedy_solution(input_data):
    sort_or_prepare(input_data)

    result = 0
    for item in input_data:
        if can_take(item):
            take(item)
            result += contribution(item)

    return result

3. Разбор задач

Задача 1: Jump Game (LeetCode 55) 🟦 Medium

Ссылка: https://leetcode.com/problems/jump-game/

Условие: Дан массив nums, где nums[i] — максимальная длина прыжка из позиции i. Определите, можно ли достичь последнего индекса, начиная с первого.

Примеры:

Ввод: nums = [2,3,1,1,4]
Вывод: true
Объяснение: Прыжок на 1 шаг от индекса 0 к 1, затем на 3 шага к последнему индексу.

Ввод: nums = [3,2,1,0,4]
Вывод: false
Объяснение: Всегда упрётесь в индекс 3, где длина прыжка = 0.

Ограничения:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁵

💡 Подсказка: Отслеживайте максимальную достижимую позицию (max_reach). Если текущая позиция > max_reach — недостижимо.

Решение:

def canJump(nums):
    max_reach = 0
    for i, num in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + num)
    return True

Объяснение:

max_reach — максимальная достижимая позиция
Если i > max_reach — не можем достичь текущей позиции
Обновляем: max_reach = max(max_reach, i + nums[i])

Сложность:

Время: O(n)
Память: O(1)

Задача 2: Jump Game II (LeetCode 45) 🟦 Medium

Ссылка: https://leetcode.com/problems/jump-game-ii/

Условие: Дан массив nums, где nums[i] — максимальная длина прыжка из позиции i. Верните минимальное количество прыжков для достижения последнего индекса.

Примеры:

Ввод: nums = [2,3,1,1,4]
Вывод: 2
Объяснение: 0→1 (1 прыжок), 1→4 (3 прыжка) = 2 прыжка

Ввод: nums = [2,3,0,1,4]
Вывод: 2

Ограничения:

1 <= nums.length <= 10⁴
0 <= nums[i] <= 1000
Гарантируется достижение последнего индекса

💡 Подсказка: Отслеживайте current_end (конец текущего диапазона) и farthest (максимальная достижимая). Увеличивайте jumps при достижении current_end.

Решение:

def jump(nums):
    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:
            jumps += 1
            current_end = farthest

    return jumps

Объяснение:

farthest — максимальная достижимая позиция
current_end — граница текущего диапазона прыжка
При i == current_end: делаем прыжок, обновляем current_end = farthest

Сложность:

Время: O(n)
Память: O(1)

Задача 3: Gas Station (LeetCode 134) 🟦 Medium

Ссылка: https://leetcode.com/problems/gas-station/

Условие: Есть n газовых станций по кругу. gas[i] — количество газа на станции i, cost[i] — газ для поездки до следующей станции.

Верните индекс начальной станции, с которой можно объехать круг. Если невозможно, верните -1.

Примеры:

Ввод: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Вывод: 3
Объяснение: Начать с станции 3, набрать 1, доехать до 4,5,0,1,2 — полный круг.

Ввод: gas = [2,3,4], cost = [3,4,3]
Вывод: -1

Ограничения:

n == gas.length == cost.length
1 <= n <= 10⁴
0 <= gas[i], cost[i] <= 10⁴

💡 Подсказка: Если sum(gas) < sum(cost) — невозможно. Иначе решение существует. Отслеживайте tank: если tank < 0, начинаем с следующей станции.

Решение:

def canCompleteCircuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1

    tank = 0
    start = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0

    return start

Объяснение:

sum(gas) < sum(cost) — необходимое условие невозможности
tank — текущий баланс газа
Если tank < 0 — не можем доехать до i, начинаем с i+1
Если решение существует, start будет правильным

Сложность:

Время: O(n)
Память: O(1)

Задача 4: Candy (LeetCode 135) 🔴 Hard

Ссылка: https://leetcode.com/problems/candy/

Условие: n детей стоят в ряд. ratings[i] — рейтинг i-го ребёнка. Раздайте конфеты по правилам:

Каждый ребёнок получает хотя бы одну конфету
Ребёнок с более высоким рейтингом получает больше соседей

Верните минимальное количество конфет.

Примеры:

Ввод: ratings = [1,0,2]
Вывод: 5
Объяснение: [2,1,2] конфеты

Ввод: ratings = [1,2,2]
Вывод: 4
Объяснение: [1,2,1] конфеты

Ограничения:

n == ratings.length
1 <= n <= 2 × 10⁴
0 <= ratings[i] <= 2 × 10⁴

💡 Подсказка: Два прохода: слева направо для возрастающих, справа налево для убывающих. candies[i] = max(left, right).

Решение:

def candy(ratings):
    n = len(ratings)
    candies = [1] * n

    # Слева направо
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1

    # Справа налево
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candies[i] = max(candies[i], candies[i+1] + 1)

    return sum(candies)

Объяснение:

Первый проход: если rating[i] > rating[i-1], candies[i] = candies[i-1] + 1
Второй проход: если rating[i] > rating[i+1], candies[i] = max(candies[i], candies[i+1] + 1)
max обеспечивает выполнение обоих условий

Сложность:

Время: O(n)
Память: O(n)

Задача 5: Interval Scheduling (LeetCode 435) 🟦 Medium

Ссылка: https://leetcode.com/problems/non-overlapping-intervals/

Условие: Дан массив интервалов intervals. Верните минимальное количество интервалов, которые нужно удалить, чтобы оставшиеся не пересекались.

Примеры:

Ввод: intervals = [[1,2],[2,3],[3,4],[1,3]]
Вывод: 1
Объяснение: Удалить [1,3]

Ввод: intervals = [[1,2],[1,2],[1,2]]
Вывод: 2

Ввод: intervals = [[1,2],[2,3]]
Вывод: 0

Ограничения:

1 <= intervals.length <= 10⁵
intervals[i].length == 2
-5 × 10⁴ <= start < end <= 5 × 10⁴

💡 Подсказка: Сортировка по концу интервала. Жадный выбор: всегда выбираем интервал с earliest finish time.

Решение:

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])  # Сортировка по концу

    count = 0
    end = float('-inf')

    for start, finish in intervals:
        if start >= end:
            end = finish  # Не пересекается
        else:
            count += 1  # Пересекается, удаляем

    return count

Объяснение:

Сортировка по концу интервала (x[1])
end — конец последнего выбранного интервала
Если start >= end — не пересекается, выбираем
Иначе — пересекается, удаляем (count += 1)

Сложность:

Время: O(n log n)
Память: O(1)

Задача 6: Merge Intervals (LeetCode 56) 🟦 Medium

Ссылка: https://leetcode.com/problems/merge-intervals/

Условие: Дан массив интервалов intervals. Объедините все пересекающиеся интервалы.

Примеры:

Ввод: intervals = [[1,3],[2,6],[8,10],[15,18]]
Вывод: [[1,6],[8,10],[15,18]]
Объяснение: [1,3] и [2,6] пересекаются → [1,6]

Ввод: intervals = [[1,4],[4,5]]
Вывод: [[1,5]]

Ограничения:

1 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start <= end <= 10⁴

💡 Подсказка: Сортировка по началу. Если start <= result[-1][1] — объединяем: result[-1][1] = max(end, result[-1][1]).

Решение:

def merge(intervals):
    intervals.sort()  # Сортировка по началу
    result = []

    for start, end in intervals:
        if not result or start > result[-1][1]:
            result.append([start, end])
        else:
            result[-1][1] = max(result[-1][1], end)

    return result

Объяснение:

Сортировка по началу интервала
Если start > result[-1][1] — не пересекается, добавляем
Иначе — пересекается, объединяем: max(end, result[-1][1])

Сложность:

Время: O(n log n)
Память: O(n)

Задача 7: Insert Interval (LeetCode 57) 🟦 Medium

Ссылка: https://leetcode.com/problems/insert-interval/

Условие: Дан массив непересекающихся интервалов intervals (отсортирован по началу) и новый интервал newInterval. Вставьте newInterval и объедините пересекающиеся.

Примеры:

Ввод: intervals = [[1,3],[6,9]], newInterval = [2,5]
Вывод: [[1,5],[6,9]]

Ввод: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Вывод: [[1,2],[3,10],[12,16]]

Ограничения:

0 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start <= end <= 10⁵

💡 Подсказка: Три этапа: 1) Интервалы до newInterval. 2) Объединение пересекающихся. 3) Интервалы после.

Решение:

def insert(intervals, newInterval):
    result = []
    i = 0
    n = len(intervals)

    # Интервалы до newInterval
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Объединение пересекающихся
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1

    result.append(newInterval)

    # Интервалы после
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

Объяснение:

Первый цикл: интервалы, заканчивающиеся до newInterval
Второй цикл: объединение всех пересекающихся с newInterval
Третий цикл: оставшиеся интервалы

Сложность:

Время: O(n)
Память: O(n)

Задача 8: Maximum Subarray (LeetCode 53) 🟦 Medium

Ссылка: https://leetcode.com/problems/maximum-subarray/

Условие: Дан целочисленный массив nums. Найдите подмассив с максимальной суммой и верните эту сумму.

Примеры:

Ввод: nums = [-2,1,-3,4,-1,2,1,-5,4]
Вывод: 6
Объяснение: [4,-1,2,1] имеет сумму 6

Ввод: nums = [1]
Вывод: 1

Ввод: nums = [5,4,-1,7,8]
Вывод: 23

Ограничения:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

💡 Подсказка: Алгоритм Кадане: current = max(num, current + num). Либо начинаем новый подмассив, либо продолжаем.

Решение:

def maxSubArray(nums):
    max_sum = current = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)
        max_sum = max(max_sum, current)
    return max_sum

Объяснение:

current — максимальная сумма подмассива, заканчивающегося в текущей позиции
current = max(num, current + num): либо начинаем новый, либо продолжаем
max_sum отслеживает глобальный максимум

Сложность:

Время: O(n)
Память: O(1)

Задача 9: Best Time to Buy and Sell Stock II (LeetCode 122) 🟦 Medium

Ссылка: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

Условие: Дан массив prices, где prices[i] — цена акции в день i. Вы можете совершать много транзакций (купить/продать). Верните максимальную прибыль.

Примеры:

Ввод: prices = [7,1,5,3,6,4]
Вывод: 7
Объяснение: Купить день 2 (1), продать день 3 (5) = 4. Купить день 4 (3), продать день 5 (6) = 3. Итого 7.

Ввод: prices = [1,2,3,4,5]
Вывод: 4

Ввод: prices = [7,6,4,3,1]
Вывод: 0

Ограничения:

1 <= prices.length <= 3 × 10⁴
0 <= prices[i] <= 10⁴

💡 Подсказка: Возьмите все восходящие отрезки: profit += prices[i] - prices[i-1] для всех i, где prices[i] > prices[i-1].

Решение:

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    return profit

Объяснение:

Суммируем все восходящие отрезки
prices[i] > prices[i-1] — цена выросла, берём прибыль
Это эквивалентно покупке на минимуме и продаже на максимуме

Сложность:

Время: O(n)
Память: O(1)

Задача 10: Partition Labels (LeetCode 763) 🟦 Medium

Ссылка: https://leetcode.com/problems/partition-labels/

Условие: Дана строка s. Разбейте её на максимальное количество частей так, чтобы каждая буква встречалась только в одной части.

Верните список размеров частей.

Примеры:

Ввод: s = "ababcbacadefegdehijhklij"
Вывод: [9,7,8]
Объяснение: "ababcbaca", "defegde", "hijhklij"

Ввод: s = "eccbbbbdec"
Вывод: [10]

Ограничения:

1 <= s.length <= 500
s из строчных английских букв

💡 Подсказка: last[c] — последняя позиция символа c. При проходе: end = max(end, last[c]). Когда i == end — конец партиции.

Решение:

def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}
    result = []
    start = end = 0

    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            result.append(end - start + 1)
            start = i + 1

    return result

Объяснение:

last[c] — последняя позиция каждого символа
end — максимальная последняя позиция символов в текущей партиции
Когда i == end — все символы текущей партиции не встречаются дальше

Сложность:

Время: O(n)
Память: O(1) (26 символов)

Задача 11: Valid Parenthesis String (LeetCode 678) 🔴 Hard

Ссылка: https://leetcode.com/problems/valid-parenthesis-string/

Условие: Дана строка s с '(', ')' и ''. '' может быть '(', ')' или пустой строкой. Проверьте валидность строки.

Примеры:

Ввод: s = "()"
Вывод: true

Ввод: s = "(*)"
Вывод: true

Ввод: s = "(*))"
Вывод: true

Ограничения:

1 <= s.length <= 100
s[i] — '(', ')' или '*'

💡 Подсказка: lo и hi — минимальное и максимальное количество открытых скобок. lo считаем '*' как ')', hi как '('.

Решение:

def checkValidString(s):
    lo = hi = 0
    for c in s:
        lo += 1 if c == '(' else -1
        hi += 1 if c != ')' else -1

        if hi < 0:
            return False
        lo = max(lo, 0)

    return lo == 0

Объяснение:

lo — минимум открытых (считаем '*' как ')')
hi — максимум открытых (считаем '*' как '(')
hi < 0 — слишком много ')', невозможно
lo = max(lo, 0) — lo не может быть отрицательным
lo == 0 в конце — можно сбалансировать

Сложность:

Время: O(n)
Память: O(1)

Задача 12: Lemonade Change (LeetCode 860) 🟦 Easy

Ссылка: https://leetcode.com/problems/lemonade-change/

Условие: Лимонад стоит $5. Покупатели платят $5, $10 или $20. У вас нет сдачи изначально. Верните true, если можете дать сдачу каждому.

Примеры:

Ввод: bills = [5,5,5,10,20]
Вывод: true
Объяснение: Три $5, затем $10 → сдача $5, затем $20 → сдача $10+$5

Ввод: bills = [5,5,10,10,20]
Вывод: false
Объяснение: После двух $5 и двух $10, для $20 нужна сдача $15, но есть только две $10

Ограничения:

1 <= bills.length <= 10⁵
bills[i] — 5, 10 или 20

💡 Подсказка: Для $15 сдачи приоритет: $10 + $5 (сохраняем $5), иначе три $5.

Решение:

def lemonadeChange(bills):
    five = ten = 0

    for bill in bills:
        if bill == 5:
            five += 1
        elif bill == 10:
            if not five:
                return False
            five -= 1
            ten += 1
        else:  # bill == 20
            if ten and five:
                ten -= 1
                five -= 1
            elif five >= 3:
                five -= 3
            else:
                return False

    return True

Объяснение:

five, ten — количество купюр
$5: просто добавляем
$10: нужна сдача $5
$20: приоритет $10 + $5 (сохраняем $5 для $10), иначе три $5

Сложность:

Время: O(n)
Память: O(1)

4. Шпаргалка

Задача	Жадный выбор
Jump Game	Максимальная досягаемость
Jump Game II	Границы диапазона прыжка
Gas Station	Если tank < 0 — новая стартовая
Candy	Два прохода: left→right, right→left
Interval Scheduling	Раннее окончание
Merge Intervals	start <= prev.end
Maximum Subarray	max(num, current + num)
Buy Stock II	Все восходящие отрезки
Partition Labels	last[c], end = max
Valid Parenthesis	lo, hi диапазон
Lemonade Change	Приоритет $10 + $5

6. ⚠️ Common Mistakes

❌ Ошибка 1: Жадность без доказательства

Проблема: Предполагают, что жадность работает, без доказательства.

# ❌ Неправильно — жадность не всегда работает
# Задача: 0/1 Knapsack
# Жадный выбор по весу или ценности НЕ даёт оптимальное решение!

# ✅ Правильно — DP для 0/1 Knapsack
# Жадность работает только для fractional knapsack

Почему это неправильно: Жадность требует доказательства корректности.

Как обнаружить: Контрпримеры дают лучший результат.

❌ Ошибка 2: Неправильная сортировка

Проблема: Сортируют не по тому ключу.

# ❌ Неправильно для Interval Scheduling
intervals.sort(key=lambda x: x[0])  # По началу!

# ✅ Правильно
intervals.sort(key=lambda x: x[1])  # По окончанию!

Почему это неправильно: Раннее окончание оставляет больше места.

❌ Ошибка 3: Пропуск проверки суммы gas

Проблема: Не проверяют необходимую условие для Gas Station.

# ❌ Неправильно
def canCompleteCircuit(gas, cost):
    start = 0
    tank = 0
    # Нет проверки sum(gas) >= sum(cost)!

# ✅ Правильно
def canCompleteCircuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1  # Невозможно!

Почему это неправильно: Если газа меньше, чем нужно, решение невозможно.

❌ Ошибка 4: Один проход вместо двух для Candy

Проблема: Не учитывают оба направления.

# ❌ Неправильно
def candy(ratings):
    candies = [1] * n
    for i in range(1, n):  # Только слева направо!
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1

# ✅ Правильно
def candy(ratings):
    candies = [1] * n
    for i in range(1, n):  # Слева направо
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1
    for i in range(n-2, -1, -1):  # Справа налево
        if ratings[i] > ratings[i+1]:
            candies[i] = max(candies[i], candies[i+1] + 1)

Почему это неправильно: Нужно учесть оба направления.

❌ Ошибка 5: Неправильный подсчёт шагов для Jump Game II

Проблема: Увеличивают jumps на каждой позиции.

# ❌ Неправильно
for i in range(n):
    jumps += 1  # На каждой позиции!

# ✅ Правильно
for i in range(n - 1):
    farthest = max(farthest, i + nums[i])
    if i == current_end:  # Только на границе
        jumps += 1
        current_end = farthest

Почему это неправильно: jumps должен увеличиваться только при смене диапазона.

7. 🎯 Попробуйте сами

Задача для самостоятельного решения

Условие: Вы планируете прыжки по массиву. Каждый элемент — максимальная длина прыжка. Найдите минимальное количество прыжков для достижения конца.

Пример:

Ввод: nums = [2,3,1,1,4]
Вывод: 2
Объяснение: 0→1 (прыжок 2), 1→4 (прыжок 3)

💡 Подсказка 1

Используйте жадный подход с границами диапазона

💡 Подсказка 2

Поддерживайте current_end и farthest

💡 Подсказка 3

Увеличивайте jumps только когда i == current_end

✅ Решение

def jump(nums):
    if len(nums) <= 1:
        return 0
    
    jumps = 0
    current_end = 0
    farthest = 0
    
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        
        if i == current_end:
            jumps += 1
            current_end = farthest
    
    return jumps

# Пример:
# nums = [2,3,1,1,4]
# i=0: farthest=2, i==current_end → jumps=1, current_end=2
# i=1: farthest=4
# i=2: farthest=4, i==current_end → jumps=2, current_end=4
# return 2

Объяснение:

farthest — максимальная достижимая позиция
current_end — граница текущего диапазона прыжка
Увеличиваем jumps только на границе диапазона

Сложность:

Время: O(n)
Память: O(1)

8. Заключение

Greedy требует доказательства, что локальный оптимум ведёт к глобальному.

Ключевые принципы:

Сортировка для правильного порядка обработки
Локально оптимальный выбор на каждом шаге
Проверка на контрпримерах

Проверьте свои знания

Вопросы ещё не добавлены

Вопросы для этой подтемы ещё не добавлены.

Задача

Greedy

Dynamic Programming

Brute Force

Interval Scheduling

✅ O(n log n)

⚠️ O(n²)

❌ O(2^n)

Coin Change (US coins)

✅ O(n)

⚠️ O(n × amount)

❌ O(2^n)

Knapsack (fractional)

✅ O(n log n)

❌ Не применимо

❌ O(2^n)

Knapsack (0/1)

❌ Не работает

✅ O(n × W)

❌ O(2^n)

Ввод: nums = [2,3,1,1,4] Вывод: true Объяснение: Прыжок на 1 шаг от индекса 0 к 1, затем на 3 шага к последнему индексу. Ввод: nums = [3,2,1,0,4] Вывод: false Объяснение: Всегда упрётесь в индекс 3, где длина прыжка = 0.

Ввод: gas = [1,2,3,4,5], cost = [3,4,5,1,2] Вывод: 3 Объяснение: Начать с станции 3, набрать 1, доехать до 4,5,0,1,2 — полный круг. Ввод: gas = [2,3,4], cost = [3,4,3] Вывод: -1

Ввод: intervals = [[1,2],[2,3],[3,4],[1,3]] Вывод: 1 Объяснение: Удалить [1,3] Ввод: intervals = [[1,2],[1,2],[1,2]] Вывод: 2 Ввод: intervals = [[1,2],[2,3]] Вывод: 0

Ввод: intervals = [[1,3],[2,6],[8,10],[15,18]] Вывод: [[1,6],[8,10],[15,18]] Объяснение: [1,3] и [2,6] пересекаются → [1,6] Ввод: intervals = [[1,4],[4,5]] Вывод: [[1,5]]

Ввод: prices = [7,1,5,3,6,4] Вывод: 7 Объяснение: Купить день 2 (1), продать день 3 (5) = 4. Купить день 4 (3), продать день 5 (6) = 3. Итого 7. Ввод: prices = [1,2,3,4,5] Вывод: 4 Ввод: prices = [7,6,4,3,1] Вывод: 0

Ввод: bills = [5,5,5,10,20] Вывод: true Объяснение: Три $5, затем $10 → сдача $5, затем $20 → сдача $10+$5 Ввод: bills = [5,5,10,10,20] Вывод: false Объяснение: После двух $5 и двух $10, для $20 нужна сдача $15, но есть только две $10

Задача

Жадный выбор

Jump Game

Максимальная досягаемость

Jump Game II

Границы диапазона прыжка

Gas Station

Если tank < 0 — новая стартовая

Candy

Два прохода: left→right, right→left

Interval Scheduling

Раннее окончание

Merge Intervals

start <= prev.end

Maximum Subarray

max(num, current + num)

Buy Stock II

Все восходящие отрезки

Partition Labels

last[c], end = max

Valid Parenthesis

lo, hi диапазон

Lemonade Change

Приоритет $10 + $5