O que o algoritmo para este problema?

Question

Recentemente fui confrontado com uma hackerrank entrevista de teste onde eu não poderia resolver o seguinte problema corretamente.Eu não gostaria de nome o problema exato para fins de privacidade, mas posso dizer que nada no Google com esse nome.

Problema

Queremos organizar um evento com o máximo de artistas possível.É-nos dada uma lista de possíveis performer horários de chegada e de desempenho de duração.A nossa função deve retornar o número máximo de artistas que pode ser selecionado sem conflitos.

Exemplo

N = 5
chegadas = [1, 3, 3, 5, 7] (artistas chegar nestes tempos)
duração = [2, 2, 1, 2, 1] (o tempo necessário para concluir suas performances)
solução = 4

Então, no momento 1, podemos aceitar o artista, e vai terminar no tempo 3.No momento 3, temos duas escolhas conflitantes, e não importa o que escolhemos.Tempo de 5 e 7 não estão em conflito qualquer.

A minha solução

1. Feitas as tuplas das chegadas e durações pelo fechando.Classificadas as tuplas primeiro na chegada, em seguida, à duração.
2. Exterior para o ciclo i do início ao fim.Inicializar o novo conjunto em cada iter.
3. Interior, para o ciclo para j de i a concluir.Verifique se j pode ser adicionado ao conjunto, sem conflito.Se o conjunto for maior do que max me salvar.

Origem Python

Perguntas

1. Existem maneiras melhores, padrão de algoritmos para resolver este problema?
2. Eu sei que existem alguns casos extremos, para que o meu algoritmo não funciona.Hackerrank avaliados meu algo, e ele só passou 7/13 casos de teste.O que poderia ser alguns casos extremos eu estou ausente?
3. É este um problema de pesquisa ou um problema de otimização?

Answer 1

Este é um simples Intervalo De Agendamento De Maximização problema que pode ser resolvido em O(n log(n)) tempo através de um simples algoritmo ganancioso.O truque é classificar performances de acordo com fim do horário de e não hora de início.

Aqui é a descrição da solução encontrada na página da Wikipédia que eu ligado:

---

Vários algoritmos, que pode parecer promissor, à primeira vista, realmente não encontrar a solução ideal:

• Selecionando intervalos que começar mais cedo não é uma solução ideal, porque se os primeiros intervalo acontece por muito tempo, aceitando-gostaria de fazer-nos rejeitar muitos outros mais curtos pedidos.

• Selecionando o menor intervalo ou selecção de intervalos com o menor número de conflitos também não é o ideal.

Ganancioso polinômio de solução

O seguinte algoritmo ganancioso não encontrar a solução ideal:

Select the interval, x, with the earliest finishing time.
Remove x, and all intervals intersecting x, from the set of candidate intervals.
Repeat until the set of candidate intervals is empty.

Sempre que selecionar um intervalo de, no passo 1, podemos ter de remover os intervalos na etapa 2.No entanto, todos estes intervalos, necessariamente, atravessar o tempo final do x, e assim todos eles se cruzam.Daí, no máximo, 1 estes intervalos podem ser a solução ideal.Assim, para cada intervalo, a melhor solução, há um intervalo de, no ganancioso solução.Isto prova que o algoritmo ganancioso, de fato, encontrar uma solução ótima.

De um modo mais formal explicação é dada por um Carregamento argumento.

O algoritmo ganancioso pode ser executado em tempo O(n log n), onde n é o número de tarefas, utilizando um pré-processamento a etapa em que as tarefas são ordenadas por seus tempos de acabamento.

---

Answer 2

Olha para Agendamento de intervalo máximo .

Atribuir um intervalo $ (s_i, t_i) $ para cada executante, para $ i= 1, \ pontos, N $ , o que significa que o desempenho começa no tempo $ s_i $ e tem uma duração da $ t_i - s_i $ .

Suponha por enquanto todos os intervalos são classificados pelo tempo final. Apenas para simplificar assumir também que todos os horários são distintos (essa suposição é desnecessária). Seu problema pode ser resolvido em $ o (n) $ tempo.

Considere $ (s_1, t_1) $ e deixe $ i $ ser o conjunto de intervalos que intersecti (excluindo $ (s_1, t_1) $ em si).

é fácil ver que todos os intervalos em $ i $ deve começar antes $ t_1 $ ( De outra forma, eles não se cruzariam $ (s_1, t_1) $ ) e final após $ t_1 $ ( Caso contrário, $ t_1 $ não seria o tempo final mínimo). Isso significa que todos os intervalos em $ i \ cope \ {(s_1, t_1)} $ intersect uns com os outros e, portanto, qualquer solução pode conter no máximo um deles.

Deixe $ s $ ser uma solução (isto é, um subconjunto de intervalos de pares sem interseção). É sempre possível converter $ s $ em uma nova solução $ s '$ que contém $ (S_1, T_1) $ e tal que $ | s '| \ ge | s | $ .

Se $ s \ tamp I=Fortyset $ então estamos feitos trivialmente, pois podemos escolher $ s '= S \ copo \ {(s_1, t_1) \} $ (Observe que isso também inclui o caso em que $ (s_1, t_1) \ em s $ ).

Se $ s \ tamp i \ neq \ vazio $ , deixe $ (s_i, t_i) $ Seja o intervalo exclusivo na $ s \ tamp I $ . Qualquer intervalo $ (s_j, t_j) \ in s setminus \ {(s_i, t_i) \} $ deve satisfazer qualquer $ s_j> t_i> t_1 $ ou $ s_i> t_j> t_1 $ . O último caso é realmente impossível, uma vez que contradizeria o fato de que $ (s_i, t_i) \ em s $ . Em outras palavras, se substituirmos $ (s_i, t_i) $ com $ (s_1, t_1) $ Ainda obtemos uma solução viável. Portanto, escolhemos $ s '= s \ copo \ {(s_1, t_1) \} \ setminus \ {(s_i, t_i) \} $ .

A linha inferior é que há sempre uma solução ideal que contém $ (s_1, t_1) $ . Portanto, você pode sempre adicionar $ (s_1, t_1) $ para sua solução, excluir todos os intervalos em $ s \ cope \ { (s_1, t_1) \} $ e procure a solução ideal entre os intervalos restantes. Isso equivale a executar o algoritmo ganancioso que considera os intervalos em ordem e adiciona qualquer intervalo que se encaixa.

A partir da sua instância, parece que os horários de partida já estão classificados. Neste caso, você pode fazer o truque de "inverter o tempo", ou seja, trocando os tempos de partida e final, por exemplo, alterando $ (s_i, t_i) $ em $ (- t_i, -s_i) $ , que permite obter uma $ O (n) $ -Time algoritmo pular a etapa de classificação inicial que já exigiria $ \ ômega (n \ log n) $ tempo.