Projete um algoritmo em pseudocódigo que, dado um conjunto de N intervalos (cada intervalo com campos 'inicio'…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções computacionais de problemas de diferentes áreas do conhecimento, de forma individual e colaborativa, selecionando as estruturas de dados e técnicas adequadas, aperfeiçoando e articulando saberes escolares.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Projete um algoritmo em pseudocódigo que, dado um conjunto de N intervalos (cada intervalo com campos 'inicio' e 'fim'), selecione o maior subconjunto de intervalos não sobrepostos. Indique a estrutura de dados usada e analise a complexidade.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Estruturas de dados: lista/array para armazenar os intervalos; resultado em lista; operação de ordenação por chave (fim). Pseudocódigo: 1. function SelecionarMaximo(intervalos): 2. ordenar intervalos por fim ascendente 3. selecionados := lista vazia 4. ultimoFim := -infinito 5. for cada intervalo in intervalos: 6. if intervalo.inicio >= ultimoFim: 7. selecionados.adicionar(intervalo) 8. ultimoFim := intervalo.fim 9. return selecionados Justificativa de correção: ordenar por tempo de fim e sempre escolher o intervalo com menor fim disponível é uma estratégia gulosa que maximiza o número de intervalos não sobrepostos. Pelo argumento de troca, qualquer solução ótima pode ser transformada para usar a escolha gulosa sem reduzir o número de intervalos. Complexidade: ordenar custa O(N log N); varredura linear custa O(N); complexidade total O(N log N). Espaço adicional O(N) para armazenar a lista de resultados.
Explicação
A abordagem utiliza uma estratégia gulosa ao ordenar os intervalos pelo tempo de fim, garantindo que sempre que um novo intervalo é selecionado, ele não sobrepõe os já escolhidos. Essa escolha maximiza a quantidade de intervalos não sobrepostos, pois prioriza os que terminam mais cedo, permitindo mais espaço para intervalos subsequentes. A análise de complexidade demonstra que, apesar do custo da ordenação, a solução é eficiente e utiliza espaço adicional proporcional ao número de intervalos.
Raio-X da questão
algoritmos de intervalos
avaliacao
estruturas de dados · algoritmos básicos
Revisar algoritmos de seleção de intervalos e suas complexidades.
O aluno pode confundir a lógica de seleção de intervalos, escolhendo intervalos que se sobrepõem em vez de garantir que sejam não sobrepostos.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Projete um algoritmo guloso em pseudocódigo que, dado um vetor de n intervalos [inicio, fim], selecione o maior conjunto…
- 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…
- Planeje a solução de um problema simples de programação: construir um programa que lê uma sequência de números de…
- 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 detecte conflitos de sala em uma matriz 'horarios' onde cada registro é [dia…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog