O desafio consiste em determinar se um intervalo de origem [x, y], onde y ≥ x, está completamente contido dentro da união de N intervalos de destino desordenados [x1, y1], [x2, y2], ..., [xn, yn].

Abordagem 1: Mapeamento em Eixo Linear

Esta solução utiliza uma representação discreta da reta numérica. Mapeamos os intervalos em um array booleano, onde cada índice representa uma unidade de comprimento no eixo.

A lógica baseia-se em marcar como "preenchido" cada segmento unitário pertencente aos intervalos de destino. Se, após o processamento, todos os segmentos unitários do intervalo alvo [x, y] estiverem marcados, o intervalo está coberto.

public static boolean verificarCoberturaLinear(int[][] intervalos, int inicioAlvo, int fimAlvo) {
    int limiteSuperior = 0;
    
    // Identifica a maior coordenada para definir o tamanho do eixo
    for (int[] par : intervalos) {
        if (par[1] > limiteSuperior) {
            limiteSuperior = par[1];
        }
    }

    // Se o fim do alvo ultrapassa o maior ponto conhecido, não há cobertura total
    if (fimAlvo > limiteSuperior) {
        return false;
    }

    // O array representa os segmentos unitários [i, i+1]
    boolean[] eixoReferencia = new boolean[limiteSuperior];

    for (int[] par : intervalos) {
        int de = par[0];
        int ate = par[1];
        for (int j = de; j < ate; j++) {
            eixoReferencia[j] = true;
        }
    }

    // Verifica se todos os pontos do intervalo alvo estão cobertos
    for (int i = inicioAlvo; i < fimAlvo; i++) {
        if (!eixoReferencia[i]) {
            return false;
        }
    }

    return true;
}

Abordagem 2: Ordenação e Fusão de Intervalos

Uma estratégia mais eficiente e escalável envolve a ordenação dos intervalos com base no ponto inicial. Após a ordenação, os intervalos sobrepostos ou adjacentes são mesclados para formar segmentos contínuos maiores. Por fim, verificamos se o intervalo alvo [x, y] reside inteiramente dentro de um desses segmentos mesclados.

import java.util.*;

class Intervalo {
    int inicio;
    int fim;

    Intervalo(int i, int f) {
        this.inicio = i;
        this.fim = f;
    }
}

public class GerenciadorIntervalos {

    public static boolean verificarCoberturaOtimizada(List<Intervalo> lista, int alvoX, int alvoY) {
        if (lista == null || lista.isEmpty()) return false;

        // Ordena os intervalos pelo ponto inicial
        lista.sort(Comparator.comparingInt(a -> a.inicio));

        List<Intervalo> mesclados = new ArrayList<>();
        Intervalo atual = lista.get(0);

        for (int i = 1; i < lista.size(); i++) {
            Intervalo proximo = lista.get(i);

            if (proximo.inicio <= atual.fim) {
                // Existe sobreposição, expande o intervalo atual
                atual.fim = Math.max(atual.fim, proximo.fim);
            } else {
                // Não há sobreposição, salva o atual e avança
                mesclados.add(atual);
                atual = proximo;
            }
        }
        mesclados.add(atual);

        // Verifica se algum dos intervalos mesclados contém o alvo completamente
        for (Intervalo m : mesclados) {
            if (alvoX >= m.inicio && alvoY <= m.fim) {
                return true;
            }
        }

        return false;
    }
}

A complexidade desta segunda abordagem é dominada pela ordenação, reusltando em O(N log N). A etapa de fusão e a verificação final ocorrem em tempo linear O(N), tornando-a superior para casos onde as coordenadas possuem alta magnitude, o que inviabilizaria a criação de arrays gigantescos na primeira solução.