Olá meus amigos nerds. Hoje vamos ajudar nosso amigo fotografo a descobrir quantas fotos ele precisa tirar para ter uma foto nítida de todos os objetos de sua cena. Já que é isso que o problema 11609. Foco nos pede para fazer. Mais especificamente, dados os intervalos contendo objetos que o fotografo quer fotografar, determinar qual é o mínimo de fotos que ele tem que tirar para que haja pelo menos uma foto de cada intervalo.
Solução
Esse problema é muito similar ao da semana passada (18553 - Janela). Vou usar o mesmo raciocínio que usei lá aqui.
O problema consiste em encontrar as interseções dos intervalos, pois assim eu posso tirar uma foto apenas da interseção dos intervalos e assim economizar fotos.
Pense nos intervalos ordenados pelo ponto em que eles terminam. Eu preciso de pelo menos uma foto do primeiro intervalo, sendo assim vou escolher tira-la no ponto onde este intervalo acaba. Dessa forma eu posso aproveitar essa foto para todos os intervalos subsequentes em que o ponto de inicio desses intervalos seja menor que o ponto que eu tirei a foto. Esse algoritmo é ótimo, pois eu necessariamente tenho que tirar uma foto do primeiro intervalo. Basta agora eu remover todos os intervalos que eu já tirei uma foto e repetir o passo anterior até que não sobre nenhum intervalo. De forma mais algorítmica teríamos:
Seja S o conjunto dos intervalos ordenados pela coordenada do seu ponto de fim
num_fotos = 0
pos_atual = 0
para cada intervalo X in S
if X.inicio > pos_atual
num_fotos++
pos_atual = X.fim
Observe que pos_atual marca até que ponto da reta nós já avaliamos (pensando nos intervalos sobre uma reta), ou seja, qual é o ponto em que o intervalo anterior termina. O if evita que incrementemos num_fotos caso o inicio do intervalo se sobreponha ao intervalo anterior, o que na prática é o mesmo que remover o intervalo atual da lista.
O problema consiste em encontrar as interseções dos intervalos, pois assim eu posso tirar uma foto apenas da interseção dos intervalos e assim economizar fotos.
Pense nos intervalos ordenados pelo ponto em que eles terminam. Eu preciso de pelo menos uma foto do primeiro intervalo, sendo assim vou escolher tira-la no ponto onde este intervalo acaba. Dessa forma eu posso aproveitar essa foto para todos os intervalos subsequentes em que o ponto de inicio desses intervalos seja menor que o ponto que eu tirei a foto. Esse algoritmo é ótimo, pois eu necessariamente tenho que tirar uma foto do primeiro intervalo. Basta agora eu remover todos os intervalos que eu já tirei uma foto e repetir o passo anterior até que não sobre nenhum intervalo. De forma mais algorítmica teríamos:
Seja S o conjunto dos intervalos ordenados pela coordenada do seu ponto de fim
num_fotos = 0
pos_atual = 0
para cada intervalo X in S
if X.inicio > pos_atual
num_fotos++
pos_atual = X.fim
Observe que pos_atual marca até que ponto da reta nós já avaliamos (pensando nos intervalos sobre uma reta), ou seja, qual é o ponto em que o intervalo anterior termina. O if evita que incrementemos num_fotos caso o inicio do intervalo se sobreponha ao intervalo anterior, o que na prática é o mesmo que remover o intervalo atual da lista.
Nenhum comentário:
Postar um comentário