Solução Informática - Nível Avançado - Semana 39

Solução escrita por Caique Paiva

Conhecimento prévio necessário:

• Algoritmos Gulosos

Primeiro, veja que achar a menor quantidade de intervalos que temos que remover é a mesma coisa que achar a maior quantidade de pares que podemos usar para formar uma array bonita. Dito isso, vamos achar esse máximo.

A ideia desse problema é a seguinte: Vamos criar um vector auxiliar chamado de $pair <int, int> un$, e, para cada intervalo $l_i, r_i$ e $l_j, r_j$ no conjunto, com $i < j$, primeiro, verificamos se eles se intersectam ou não, e caso se intersectem, colocamos em $un$ $[l_i ,r_i] \cup [l_j, r_j]$, que é a mesma coisa que $[min(l_i, l_j), max(r_i, r_j)]$, pois eles se intersectam. Então, em un, vamos ter várias dessas uniões de intervalos.

Com isso, vamos resolver o problema usando un, pois, pegar um elemento de un é a mesma coisa que pegar um par de segmentos. Veja as condições do problema de novo:

• Qualquer elemento da array está em exatamente um par: Como foi dito acima, achar a menos quantidade de intervalos que temos que remover é a mesma coisa que achar a maior quantidade de pares que precisamos usar, e cada par que podemos pegar está em un, logo, basta sabermos quantos elementos de un precisamos pegar no máximo
• Segmentos no mesmo par se intersectam: Em un, todos os elementos representam a união de pares de elementos, logo estamos cumprindo essa condição pegando elementos de un também
• Segmentos em pares diferentes não se intersectam: Isso significa que, se pegarmos dois pares e olharmos para a união deles, eles não vão se intersectar.

Com isso, o problema se torna achar a maior quantidade de intervalos em un que podemos pegar sem que eles se intersectem! Porém, esse é um problema clássico de cp! Caso não conheça, a solução dele está no material de algoritmos gulosos acima (É o dentista da PJ).

Clique aqui para ver o código