Жадные алгоритмы и интервалы

⏱ 40 мин · 🧩 заданий: 6

Жадная стратегия

Жадный алгоритм на каждом шаге делает локально лучший выбор и больше к нему не возвращается. Он прост и быстр (обычно сортировка + один проход, O(n log n)), но верен не всегда.

def greedy_coins(coins, amount):
    picked = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            picked.append(c)
    return picked

print(greedy_coins([1, 5, 10, 25], 63))   # для «канонических» монет верно
print(greedy_coins([1, 3, 4], 6))          # а здесь — нет: оптимум [3, 3]

Как понять, что жадность сработает? Нужно доказательство, и на собеседовании достаточно его идеи:

Аргумент обмена: возьмём любое оптимальное решение. Если оно отличается от жадного на первом шаге, заменим этот шаг на жадный — решение не ухудшится. Повторяя, превратим оптимум в жадное решение.
«Жадный не отстаёт»: после каждого шага жадное решение не хуже любого другого.

Если доказать не получается, проверьте маленький контрпример и, возможно, переходите к ДП.

Интервалы: сначала сортировка

Почти все задачи на интервалы начинаются с сортировки — по началу или по концу.

[1───3] отсортированы по началу: [2─────6] [8──10] [15──18] если start ≤ конца последнего, продлеваем его, иначе — новый [1────────6] [8──10] [15──18]

def merge_intervals(intervals):
    merged = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)    # max! [1,10] поглощает [2,3]
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1, 3], [8, 10], [2, 6], [15, 18]]))
print(merge_intervals([[1, 10], [2, 3], [4, 5]]))

def insert_interval(intervals, new):
    """Вставка в уже отсортированный список непересекающихся интервалов, O(n)."""
    result, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < new[0]:          # строго левее
        result.append(intervals[i]); i += 1
    start, end = new
    while i < n and intervals[i][0] <= end:            # пересекаются — сливаем
        start, end = min(start, intervals[i][0]), max(end, intervals[i][1]); i += 1
    result.append([start, end])
    return result + intervals[i:]

print(insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))

Закрытые или полуоткрытые?

Уточняйте у интервьюера, пересекаются ли [1, 4] и [4, 5]. Для встреч обычно нет (одна закончилась — другая началась), для отрезков на прямой — да. От этого зависит < или <= в условии.

Выбор максимума непересекающихся

Классическая задача о расписании: из множества встреч выбрать как можно больше непересекающихся. Жадный выбор — та, что раньше всех заканчивается: она оставляет больше всего времени для остальных.

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]

def schedule(meetings, key):
    chosen, free_at = [], float("-inf")
    for start, end in sorted(meetings, key=key):
        if start >= free_at:
            chosen.append((start, end))
            free_at = end
    return chosen

print("по концу: ", schedule(meetings, key=lambda m: m[1]))
print("по началу:", schedule(meetings, key=lambda m: m[0]))
print("по длине: ", schedule(meetings, key=lambda m: m[1] - m[0]))

tricky = [(1, 5), (4, 7), (6, 10)]
print("по длине: ", schedule(tricky, key=lambda m: m[1] - m[0]), "— а по концу:", schedule(tricky, key=lambda m: m[1]))

Сортировка по концу даёт 4 встречи — это оптимум. Сортировка по началу проигрывает. По длине на первом наборе случайно тоже 4, но на втором самая короткая встреча (4, 7) мешает сразу двум другим. Доказуемо верен только ключ «по концу».

Минимум переговорных: сканирующая прямая

Превратим каждую встречу в два события: «+1» в момент начала и «−1» в момент конца. Пройдём события по времени — максимум текущей суммы и есть ответ.

def min_rooms(meetings):
    events = sorted([(s, 1) for s, _ in meetings] + [(e, -1) for _, e in meetings])
    rooms = best = 0
    for time, delta in events:
        rooms += delta
        best = max(best, rooms)
        print(f"t={time:2}  {'+' if delta > 0 else '−'}  занято комнат: {rooms}")
    return best

print("нужно комнат:", min_rooms([(0, 30), (5, 10), (15, 20), (10, 15)]))

Кортежи (время, -1) сортируются раньше (время, 1), поэтому встреча, закончившаяся в 10, освобождает комнату до начала встречи в 10.

Альтернатива — min-куча концов встреч: сортируем по началу; если самая рано освобождающаяся комната свободна к началу встречи, переиспользуем её (heapreplace), иначе добавляем новую. Размер кучи в конце — ответ.

import heapq

def min_rooms_heap(meetings):
    ends = []
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)
    return len(ends)

print(min_rooms_heap([(0, 30), (5, 10), (15, 20), (10, 15)]))

Ещё жадные классики

def can_jump(nums):
    reach = 0
    for i, x in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + x)
    return True

def min_jumps(nums):
    """Минимум прыжков до конца: BFS по «уровням» без очереди."""
    jumps, cur_end, farthest = 0, 0, 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:
            jumps += 1
            cur_end = farthest
    return jumps

def gas_station(gas, cost):
    """С какой заправки можно проехать круг? Если суммарно бензина хватает — ответ есть."""
    if sum(gas) < sum(cost):
        return -1
    start, tank = 0, 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:            # из start до i+1 не доехать — и ни из какой станции между ними
            start, tank = i + 1, 0
    return start

print(can_jump([2, 3, 1, 1, 4]), can_jump([3, 2, 1, 0, 4]))
print(min_jumps([2, 3, 1, 1, 4]))
print(gas_station([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))

Жадность или ДП?

Признак	Жадный	ДП
Выбор можно сделать, не зная будущего	✔
Есть простой аргумент обмена	✔
Контрпример на маленьких данных		✔
Нужно «сколько способов»		✔
Типичная сложность	O(n log n)	O(n·W), O(n²)

Сигналы жадной задачи и задачи на интервалы

«Максимум непересекающихся», «минимум ресурсов одновременно», «слить/вставить интервалы», «можно ли дойти», «расписание». Первое действие — отсортировать и подумать, по какому ключу.

Итог

Жадный алгоритм — локально лучший выбор без пересмотра; проверяйте контрпримером, обосновывайте обменом.
Интервалы: слить — сортировка по началу; максимум непересекающихся — по концу.
Минимум комнат — сканирующая прямая или куча концов.
Если жадность ломается на маленьком примере — переходите к ДП.

Войдите, чтобы отмечать пройденные уроки.

	по началу	по концу
Слить пересекающиеся интервалы
Выбрать максимум непересекающихся интервалов
Минимум стрел, чтобы лопнуть все шарики-интервалы