Removendo Intervalos Sobrepostos (LeetCode 435)

O objetivo deste problema é determinar o número mínimo de intervalos que precisam ser removidos para que os restantes não se sobreponham. A estratégia gulosa consiste em ordenar os intervalos e, sempre que houver uma colisão, optar por manter o intervalo que termina mais cedo, maximizando o espaço para os intervalos subsequentes.

Lógica de Implementação:

• Ordene a matriz com base no ponto inicial de cada intervalo.
• Percorra a lista comparando o início do intervalo atual com o fim do anterior.
• Se houver sobreposição, incrementamos o contador de remoções e atualizamos o limite inferior do fim do intervalo para garantir que estamos "removendo" o que se estende mais à direita.

class Solution {
    public int eraseOverlapIntervals(int[][] blocos) {
        if (blocos.length == 0) return 0;

        // Ordenação por ponto de início
        Arrays.sort(blocos, (a, b) -> Integer.compare(a[0], b[0]));

        int totalRemovidos = 0;
        int fimAnterior = blocos[0][1];

        for (int i = 1; i < blocos.length; i++) {
            // Se o início atual for menor que o fim do anterior, há sobreposição
            if (blocos[i][0] < fimAnterior) {
                totalRemovidos++;
                // Mantemos o intervalo que termina primeiro (estratégia gulosa)
                fimAnterior = Math.min(fimAnterior, blocos[i][1]);
            } else {
                // Não há sobreposição, atualizamos o fim de referência
                fimAnterior = blocos[i][1];
            }
        }
        return totalRemovidos;
    }
}

Parttição de Etiquetas em Strings (LeetCode 763)

Neste desafio, devemos dividir uma string no maior número possível de partes, de modo que cada letra apareça em apenas uma parte. A abordagem gulosa foca em encontrar o limite mais disatnte de cada caractere encontrado até o momento.

Lógica de Implementação:

• Primeiro, mapeamos a última posição de ocorrência de cada letra (de 'a' a 'z').
• Percorremos a string mantendo uma variável que rastreia o ponto de fechamento necessário (o maior índice de última ocorrência entre as letras vistas na partição atual).
• Quando o índice atual alcança esse ponto de fechamento, fechamos a partição e iniciamos uma nova.

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] ultimaPosicao = new int[26];
        char[] caracteres = s.toCharArray();

        // Mapeia o último índice de cada caractere
        for (int i = 0; i < caracteres.length; i++) {
            ultimaPosicao[caracteres[i] - 'a'] = i;
        }

        List<Integer> particoes = new ArrayList<>();
        int inicioSetor = 0;
        int limiteDireito = 0;

        for (int i = 0; i < caracteres.length; i++) {
            // Atualiza o limite necessário para incluir todas as ocorrências
            limiteDireito = Math.max(limiteDireito, ultimaPosicao[caracteres[i] - 'a']);

            // Se chegamos no limite máximo, cortamos a string
            if (i == limiteDireito) {
                particoes.add(limiteDireito - inicioSetor + 1);
                inicioSetor = i + 1;
            }
        }
        return particoes;
    }
}

Fusão de Intervalos (LeetCode 56)

Dada uma coleção de intervalos, o objetivo é mesclar todos os que se sobrepõem. Diferente do problema de remoção, aqui unificamos as faixas de valores em novos blocos contínuos.

Lógica de Implementação:

• Ordene os intervalos pelo ponto enicial.
• Inicie um intervalo temporário com o primeiro elemento.
• Ao iterar, se o início do próximo intervalo for menor ou igual ao fim do intervalo atual, estendemos o fim do intervalo atual para o máximo entre os dois.
• Caso contrário, o intervalo atual está completo; adicione-o ao resultado e comece um novo.

class Solution {
    public int[][] merge(int[][] intervalos) {
        if (intervalos.length <= 1) return intervalos;

        // Ordenação por início
        Arrays.sort(intervalos, (i1, i2) -> Integer.compare(i1[0], i2[0]));

        List<int[]> resultado = new ArrayList<>();
        int[] intervaloAtual = intervalos[0];
        resultado.add(intervaloAtual);

        for (int[] proximo : intervalos) {
            int fimAtual = intervaloAtual[1];
            int inicioProximo = proximo[0];
            int fimProximo = proximo[1];

            if (inicioProximo <= fimAtual) {
                // Existe intersecção, expandimos o intervalo atual
                intervaloAtual[1] = Math.max(fimAtual, fimProximo);
            } else {
                // Não há intersecção, avançamos para o próximo bloco
                intervaloAtual = proximo;
                resultado.add(intervaloAtual);
            }
        }

        return resultado.toArray(new int[resultado.size()][]);
    }
}