Mediumgreedy
Что такое жадные алгоритмы (greedy)?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Greedy — на каждом шаге локально-оптимальный выбор без отката. Работает, когда есть optimal substructure + greedy choice property (локально оптимальный = часть глобально оптимального).
# Activity selection: максимум non-overlapping intervals
def max_activities(intervals):
intervals.sort(key=lambda x: x[1]) # по end time
count, last_end = 0, float('-inf')
for start, end in intervals:
if start >= last_end:
count += 1
last_end = end
return count
# Fractional knapsack — sort по value/weight
# Dijkstra — всегда ближайшую вершину
# Huffman coding — min-heap mergeКогда НЕ работает: 0/1 Knapsack, Coin change с произвольными номиналами (нужен DP), TSP (greedy nearest neighbor далёк от оптимума). Доказательство greedy optimality — часто через exchange argument. Greedy быстрее DP (O(n log n) typical), но требует proof.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.