Festival

Festivais de música deveriam ser pura diversão, porém alguns deles se tornam tão grandes a ponto de causar dor de cabeça para os frequentadores. O problema é que são tantas atrações boas tocando em tantos palcos que a simples tarefa de escolher quais shows assistir se torna complexa.

Para ajudar frequentadores de tais festivais, Fulano decidiu criar um aplicativo que, após avaliar as músicas ouvidas em seus serviços de streaming favoritos, sugere quais shows assistir de modo que não exista outra combinação de shows melhor de acordo com os critérios descritos a seguir:

• Para aproveitar a experiência ao máximo é importante assistir cada um dos shows escolhidos por completo;

• Ir no festival e não ver um dos palcos está fora de cogitação;

• Para garantir que a seleção dos artistas seja compatível com o usuário, contou-se quantas músicas de cada artista o usuário conhece por já ter ouvido-as nos serviços de streaming. O total de músicas conhecidas dos artistas escolhidos deve ser o maior possível.

Infelizmente a versão beta do aplicativo recebeu várias críticas, pois os usuários conseguiram pensar em seleções melhores que aquelas sugeridas. Sua tarefa nesse problema é ajudar Fulano e escrever um programa que, dadas as descrições dos shows acontecendo em cada palco, calcula a lista ideal para o usuário.

O tempo de deslocamento entre os palcos é ignorado; portanto, desde que não haja interseção entre os horários de quaisquer dois shows escolhidos considera-se que é possével assistir a todos por completo. Em particular, se um show acaba exatamente quando um outro começa, é possível assistir a ambos.