Projete um algoritmo guloso em pseudocódigo que, dado um vetor de n intervalos [inicio, fim], selecione o…

Questão

Projete um algoritmo guloso em pseudocódigo que, dado um vetor de n intervalos [inicio, fim], selecione o maior conjunto de intervalos não sobrepostos. Explique a corretude e indique a complexidade temporal.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Pseudocódigo: 1. ordenar(intervalos) por fim ascendente 2. selecionados = [] 3. ultimo_fim = -8 4. para cada I em intervalos: se I.inicio >= ultimo_fim então adicionar I em selecionados ultimo_fim = I.fim 5. retornar selecionados Corretude: argumento de troca — escolher o intervalo com menor fim deixa mais espaço para selecionar os demais; trocando o primeiro intervalo diferente por este não reduz o número total, portanto a solução gulosa é ótima. Complexidade: ordenar O(n log n) + varredura O(n) => O(n log n).

Explicação

O algoritmo é eficaz porque prioriza a seleção de intervalos com o menor tempo de término, permitindo a inclusão de mais intervalos subsequentes. Essa estratégia garante que, ao escolher um intervalo, sempre haverá espaço para outros, maximizando o conjunto final. A combinação da ordenação e da varredura resulta em uma complexidade temporal de O(n log n), que é a mais eficiente possível para este problema.

Raio-X da questão

Questões parecidas com resolução

• Uma equipe precisa gerar cem relatórios com a mesma estrutura, mudando apenas os valores das turmas e das notas. — Qual…
• No fim de semana da feira de ciências do bairro, a equipe de organização percebeu um problema repetido: dezenas de…
• Projete em pseudocódigo uma função recursiva quicksort(L) que ordena uma lista L de inteiros em ordem não crescente…
• Projete uma função recursiva em pseudocódigo flatten(L) que recebe uma lista L que pode conter inteiros e sublistas…
• Em um algoritmo, uma função recebe um vetor chamado dados que não deve ser alterado. Para garantir que a variável…
• Descreva um algoritmo em pseudocódigo que, dada uma matriz quadrada A[n][n] de inteiros e um inteiro k>0, percorra os…

Todas as questões de Estratégias de solução de problemas - Decomposição