Estratégia gulosa (Greedy).
Escolher bem agora — quando a estrutura do problema permite confiar no futuro.
Qual atividade termina primeiro?
ordenar pelo fim
proteja o horizonte.
Antes da primeira escolha, colocamos as atividades em uma ordem que preserva o maior espaço possível para o restante.
princípio /
A melhor escolha local pode levar a uma solução ótima quando existe a propriedade de escolha gulosa.
limite que não pode ser omitido
Uma estratégia gulosa não é sinônimo de “escolha o maior valor”. Sem uma prova ou propriedade adequada, a decisão local pode bloquear a melhor solução global.
A seleção custa O(n) quando as atividades já estão ordenadas; nesta implementação, ordenar a entrada com toSorted domina o custo e leva a O(n log n).
Uma escolha, um futuro.
O destaque acompanha a decisão atual. Leia o pseudocódigo antes de trocar de linguagem; a implementação é uma tradução, não um novo algoritmo.
01const ordered = activities.toSorted((a, b) => a.end - b.end);02let lastEnd = -Infinity;03return ordered.filter((activity) => {04 if (activity.start < lastEnd) return false;05 lastEnd = activity.end;06 return true;07});