Algoritmos gulosos constroem soluções através de escolhas localmente ótimas em cada etapa, assumindo que a sequência de decisões levará a um ótimo global. Essa abordagem é válida quando o problema exibe a propriedade da escolha gulosa e subestrutura ótima. A seguir, são explorados padrões algorítmicos recorrentes envolvendo manipulação de intervalos, filas de prioridade e fundamentos matemáticos aplicados à otimização.

Seleção Mínima de Pontos em Intervalos

Dado um conjunto de intervalos fechados, o objetivo é determinar a quantidade mínima de pontos na reta numérica tal que cada intervalo contenha pelo menos um ponto selecionado. A estratégia consiste em ordenar os intervalos pelo limite direito. Ao percorrer a lista, um ponto é alocado no extremo direito do primeiro intervalo não coberto. Essa posição maximiza a chance de cobrir intervalos subsequentes que se sobrepõem à direita.

#include <iostream>
#include <vector>
#include <algorithm>

struct Segment { long long start, end; };

int main() {
    int total_segments;
    std::cin >> total_segments;
    
    std::vector<Segment> ranges(total_segments);
    for (auto& seg : ranges) {
        std::cin >> seg.start >> seg.end;
    }

    std::sort(ranges.begin(), ranges.end(), [](const Segment& a, const Segment& b) {
        return a.end < b.end;
    });

    int points_count = 0;
    long long last_position = -4000000000000000000LL;

    for (const auto& curr : ranges) {
        if (last_position < curr.start) {
            points_count++;
            last_position = curr.end;
        }
    }

    std::cout << points_count << "\n";
    return 0;
}

Maximização de Intervalos Mutualmente Disjuntos

O problema dual à seleção de pontos busca extrair o maior subconjunto possível de intervalos que não compartilham nenhum ponto, incluindo extremidades. A lógica gulosa permanece idêntica: ordenação pelo limite direito e seleção iterativa. Sempre que o início do intervalo atual for estritamente maior que o fim do último intervalo aceito, ele é adicionado ao conjunto solução, garantindo a maximalidade.

#include <iostream>
#include <vector>
#include <algorithm>

struct Range { long long left, right; };

int main() {
    int n;
    std::cin >> n;
    std::vector<Range> data(n);
    for (auto& r : data) std::cin >> r.left >> r.right;

    std::sort(data.begin(), data.end(), [](const Range& x, const Range& y) {
        return x.right < y.right;
    });

    int compatible_count = 0;
    long long boundary = -4000000000000000000LL;

    for (const auto& item : data) {
        if (item.left > boundary) {
            compatible_count++;
            boundary = item.right;
        }
    }

    std::cout << compatible_count << "\n";
    return 0;
}

Agrupamento Ótimo de Intervalos

Quando é necessário particionar intervalos em grupos onde nenhum par dentro do mesmo grupo se intersecta, minimizando o número total de grupos, a abordagem muda. Os intervalos são ordenados pelo limite esquerdo. Uma fila de prioridade mínima (min-heap) armazena os limites direitos dos grupos ativos. Para cada novo intervalo, se seu início for maior que o menor limite direito no topo da heap, ele pode ser alocado nesse grupo (atualizando o topo). Caso contrário, um novo grupo é criado.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

struct Interval { long long l, r; };

int main() {
    int qty;
    std::cin >> qty;
    std::vector<Interval> arr(qty);
    for (auto& iv : arr) std::cin >> iv.l >> iv.r;

    std::sort(arr.begin(), arr.end(), [](const Interval& a, const Interval& b) {
        return a.l < b.l;
    });

    std::priority_queue<long long, std::vector<long long>, std::greater<long long>> group_ends;

    for (const auto& curr : arr) {
        if (!group_ends.empty() && group_ends.top() < curr.l) {
            group_ends.pop();
        }
        group_ends.push(curr.r);
    }

    std::cout << group_ends.size() << "\n";
    return 0;
}

Cobertura Completa de Segmentos

Para cobrir um segmento alvo [S, T] utilizando a menor quantidade de intervalos disponíveis, ordena-se a entrada pelo limite esquerdo. Iterativamente, seleciona-se o intervalo que começa antes ou no ponto de cobertura atual e estende-se mais à direita. O ponto de cobertura é atualizado para esse novo extremo direito. Se em algum momento não houver intervalo válido para estender a cobertura, a solução é inviável.

#include <iostream>
#include <vector>
#include <algorithm>

struct Span { long long l, r; };

int main() {
    long long target_l, target_r;
    std::cin >> target_l >> target_r;
    
    int m;
    std::cin >> m;
    std::vector<Span> pool(m);
    for (auto& s : pool) std::cin >> s.l >> s.r;

    std::sort(pool.begin(), pool.end(), [](const Span& a, const Span& b) {
        return a.l < b.l;
    });

    int selected = 0;
    long long current_edge = target_l;
    bool success = false;

    for (int idx = 0; idx < m; ) {
        long long best_reach = -4000000000000000000LL;
        while (idx < m && pool[idx].l <= current_edge) {
            best_reach = std::max(best_reach, pool[idx].r);
            idx++;
        }

        if (best_reach < current_edge) break;

        selected++;
        current_edge = best_reach;
        if (current_edge >= target_r) {
            success = true;
            break;
        }
    }

    std::cout << (success ? selected : -1) << "\n";
    return 0;
}

Construção de Árvores de Huffman com Filas de Prioridade

Probelmas de fusão sequencial onde o custo de cada operação é a soma dos elementos combinados são resolvidos otimamente através da estrutura de Huffman. A estratégia gulosa dita que os dois menores valores disponíveis devem ser mesclados primeiro. Uma min-heap gerencia essa extração eficiente. O processo repete-se até restar um único elemento, acumulando os custos intermediários.

#include <iostream>
#include <queue>
#include <vector>

int main() {
    int elements;
    std::cin >> elements;
    
    std::priority_queue<long long, std::vector<long long>, std::greater<long long>> min_heap;
    for (int i = 0; i < elements; ++i) {
        long long val;
        std::cin >> val;
        min_heap.push(val);
    }

    long long accumulated_cost = 0;
    while (min_heap.size() > 1) {
        long long first = min_heap.top(); min_heap.pop();
        long long second = min_heap.top(); min_heap.pop();
        long long combined = first + second;
        accumulated_cost += combined;
        min_heap.push(combined);
    }

    std::cout << accumulated_cost << "\n";
    return 0;
}

Padrões Matemáticos: Desigualdades de Ordenação e Valor Absoluto

Certos problemas de minimização reduzem-se a propriedades algébricas diretas, dispensando estruturas complexas.

Minimização de Tempo de Espera (Desigualdade de Rearranjo)

Para minimizar a soma dos tempos de espera em uma fila única, tarefas com menor duração devem ser processadas primeiro. Ordenando os tempos crescentemente, o custo total é calculado ponderando cada duração pelo número de pessoas que aguardam após ela.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int n;
    std::cin >> n;
    std::vector<long long> durations(n);
    for (auto& t : durations) std::cin >> t;

    std::sort(durations.begin(), durations.end());

    long long total_wait = 0;
    for (int i = 0; i < n; ++i) {
        total_wait += durations[i] * (n - 1 - i);
    }

    std::cout << total_wait << "\n";
    return 0;
}

Localização Ótima por Distância Manhattan (Mediana)

Minimizar a soma das distâncias absolutas entre um ponto escolhido e um conjunto de coordenadas na reta é resolvido selecionando a mediana das posições. A mediana equilibra a quantidade de pontos à esquerda e à direita, anulando derivadas subgradientes da função objetivo L1.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

int main() {
    int n;
    std::cin >> n;
    std::vector<long long> coords(n);
    for (auto& c : coords) std::cin >> c;

    std::sort(coords.begin(), coords.end());
    long long median_pos = coords[n / 2];
    
    long long distance_sum = 0;
    for (long long pos : coords) {
        distance_sum += std::abs(pos - median_pos);
    }

    std::cout << distance_sum << "\n";
    return 0;
}

Argumento de Troca e Minimização de Risco Máximo

Em problemas de empilhamento onde cada elemento possui peso e resistência, e o risco é definido como a soma dos pesos acima menos a resistência própria, a ordenação ótima é derivada via argumento de troca. Comparando dois elementos adjacentes i e j, a configuração que minimiza o pico de risco local ocorre quando peso[i] + resistencia[i] < peso[j] + resistencia[j]. Ordenando toda a coleção por essa soma crescente e calculando os riscos com prefixos de peso acumulaods, obtém-se o mínimo global do valor máximo.

#include <iostream>
#include <vector>
#include <algorithm>

struct Animal { long long mass, tolerance; };

int main() {
    int count;
    std::cin >> count;
    std::vector<Animal> herd(count);
    for (auto& a : herd) std::cin >> a.mass >> a.tolerance;

    std::sort(herd.begin(), herd.end(), [](const Animal& x, const Animal& y) {
        return x.mass + x.tolerance < y.mass + y.tolerance;
    });

    long long peak_risk = -4000000000000000000LL;
    long long load_above = 0;

    for (const auto& creature : herd) {
        peak_risk = std::max(peak_risk, load_above - creature.tolerance);
        load_above += creature.mass;
    }

    std::cout << peak_risk << "\n";
    return 0;
}