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