Greedy Algorithms (Жадные алгоритмы)
Когда применять:
- Нужно делать локально оптимальный выбор на каждом шаге.
- Часто используется с интервалами или когда нужно что-то максимизировать/минимизировать без полного перебора.
- Сортировка — часто первый шаг в жадном решении.
Интервалы (Intervals)
Задача: Объединить пересекающиеся интервалы.
// 1. Сортируем по началу
intervals.sort((a, b) => a[0] - b[0]);
const res = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = res[res.length - 1];
const curr = intervals[i];
if (curr[0] <= last[1]) {
// Перекрытие -> Продлеваем конец предыдущего
last[1] = Math.max(last[1], curr[1]);
} else {
// Нет перекрытия -> Добавляем новый
res.push(curr);
}
}Покупка акций (Stock Trading)
Задача: Максимизировать прибыль, покупая и продавая много раз.
// Просто суммируем все положительные изменения цены
let profit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1]) {
profit += prices[i] - prices[i-1];
}
}
return profit;