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

• Projete um algoritmo em pseudocódigo que, dado um conjunto de N intervalos (cada intervalo com campos 'inicio' e 'fim')…
• Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros e um inteiro k (1 = k = n), calcule a maior…
• Descreva em pseudocódigo um algoritmo que receba uma matriz M de m×n inteiros (linhas = bairros, colunas = dias) e…
• Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros, encontre o comprimento do maior subvetor…
• Projete um algoritmo em pseudocódigo que, dado um vetor V de n inteiros e um inteiro k, determine se existem índices i <…
• Descreva em pseudocódigo um algoritmo que detecte conflitos de sala em uma matriz 'horarios' onde cada registro é [dia…

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