Activity Selection Problem
A atividade i vai do horário start[i] ao horário finish[i]. Uma pessoa realiza uma atividade por vez, e a próxima atividade deve começar estritamente depois que a anterior terminar: uma atividade que começa exatamente no horário em que outra termina não pode ser realizada em seguida.
Retorne o maior número de atividades que uma pessoa pode realizar.
Função
- startinteger-array
- o horário de início de cada atividade
- finishinteger-array
- o horário de término de cada atividade; finish[i] corresponde a start[i]
- Retornainteger
- o maior número de atividades que uma pessoa pode fazer, uma após a outra
Restrições
1 ≤ start.length == finish.length ≤ 50000 ≤ start[i] ≤ finish[i] ≤ 105- Uma atividade pode começar e terminar ao mesmo tempo. Os vetores não estão ordenados.
Exemplos
- Entrada
- start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
- Saída
- 4
- Explicação
- Fazer de 10 a 13, de 14 a 19, de 21 a 22 e de 25 a 30 resulta em 4. Cinco é impossível: de 10 a 13 entra em conflito com de 12 a 16, e de 21 a 22 com de 20 a 24.
- Entrada
- start = [1, 5, 9]finish = [5, 9, 12]
- Saída
- 2
- Explicação
- A atividade das 5 às 9 começa exatamente no horário em que a primeira termina, então ela não pode vir depois dela. Fazer a atividade das 1 às 5 e depois a das 9 às 12 funciona, então a resposta é
2.
- Entrada
- start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
- Saída
- 3
- Explicação
- A atividade de 0 a 100 se sobrepõe a todas as outras. Deixando-a de fora, 2 a 4, 5 a 7 e 8 a 10 se encaixam uma após a outra:
3.
Para ir além
Duas pessoas agora trabalham em paralelo, cada uma realizando uma atividade por vez. Quantas atividades elas podem realizar juntas e qual pessoa deve ficar responsável por cada uma?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Suponha que você já saiba qual atividade fará primeiro. Qual você gostaria que fosse, para que reste o máximo de tempo possível depois?
A atividade que termina primeiro é sempre uma escolha inicial segura: um plano que começa com qualquer outra atividade pode substituí-la pela que termina primeiro e manter a mesma quantidade. Depois disso, a mesma pergunta se repete para as atividades que começam após o término dela.
Ordene as atividades pelo horário de término, movendo cada início junto com seu término. Percorra a lista ordenada mantendo o horário de término da última atividade que você selecionou e selecione todas as atividades cujo início seja estritamente maior que esse horário.
Solução
Testar todos os subconjuntos de atividades leva tempo exponencial. Uma regra gulosa resolve a questão: entre as atividades que ainda cabem, sempre faça aquela que termina primeiro. Ordenar pelo horário de término transforma essa regra em uma única passagem.
Escolha o término mais cedo, repetidamente
Correta, mas não termina nos maiores testes
Intuição
A atividade que termina mais cedo de todas é uma primeira escolha pelo menos tão boa quanto qualquer outra. Ela não libera você mais tarde, então tudo o que poderia vir depois de outra primeira escolha também pode vir depois dela, e trocá-la pela outra mantém a quantidade. Depois dessa escolha, o problema se repete com as atividades que começam depois que ela termina.
No primeiro exemplo, você escolhe de 10 a 13, depois de 14 a 19, depois de 21 a 22 e, por fim, de 25 a 30: quatro.
Cada escolha percorre todas as n atividades, então o custo é n vezes a resposta. Quando todas as 5000 atividades cabem uma após a outra, são 25 milhões de verificações.
Algoritmo
- Defina
count = 0elastFinish = -1, abaixo de cada início. - Percorra todas as atividades e encontre aquela com
start[i] > lastFinishque termina primeiro. - Se não houver nenhuma, retorne
count. - Caso contrário, adicione 1 a
count, definalastFinishcomo o término dessa atividade e percorra novamente.
def maxActivities(start, finish):
n = len(start)
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
while True:
# among the activities that start after last_finish, find the one that ends first
pick = -1
for i in range(n):
if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
pick = i
if pick == -1:
return count
count += 1
last_finish = finish[pick]Ordene pelo horário de término e selecione de forma gulosa
Intuição
Ordene uma vez pelo horário de término e você encontrará as atividades na ordem em que as varreduras acima as procuraram. Percorra a lista ordenada mantendo lastFinish, o horário de término da última atividade que você escolheu. Uma atividade com start[i] > lastFinish é a que termina mais cedo entre as que ainda cabem, então escolha-a. Qualquer outra entra em conflito com sua última escolha, então ignorá-la não custa nada.
Em ordem, o primeiro exemplo fica assim: 10 a 13, 12 a 16, 14 a 19, 21 a 22, 20 a 24, 25 a 30. Você escolhe a primeira, a terceira, a quarta e a sexta: 12 não é posterior a 13, e 20 não é posterior a 22.
Não é preciso definir uma regra para empates no horário de término. Depois que você escolhe uma atividade que termina em t, todas as outras que terminam em t começam em t ou antes e são ignoradas.
Algoritmo
- Ordene as atividades por
finish, movendo cada início junto com seu término. - Defina
count = 0elastFinish = -1. - Para cada atividade nessa ordem, se
start[i] > lastFinish, some 1 acounte definalastFinish = finish[i]. - Retorne
count.
def maxActivities(start, finish):
order = sorted(range(len(start)), key=lambda i: finish[i]) # earliest finish first
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
for i in order:
if start[i] > last_finish:
count += 1
last_finish = finish[i]
return count
Armadilhas e casos extremos
- Ordenar pelo horário de início. No terceiro exemplo, a atividade de 0 a 100 começa primeiro e bloqueia as outras três.
- Escolher primeiro a atividade mais curta. Com as atividades de 1 a 5, de 5 a 6 e de 6 a 10, a mais curta é de 5 a 6, que conflita com as outras duas; as atividades de 1 a 5 e de 6 a 10 resultam em 2.
- Comparar usando
≥em vez de>. No segundo exemplo, isso retorna 3 em vez de 2. - Ordenar
finishsozinho. Cada início precisa acompanhar seu próprio término, ou os horários de início serão associados às atividades erradas. - Iniciar
lastFinishem 0. Uma única atividade de 0 a 1 será ignorada, porque0 > 0é falso.
Perguntas frequentes3
Qual é a complexidade de tempo do problema de seleção de atividades?
Ordenar pelo horário de término custa O(n log n), e a etapa gulosa depois disso é O(n), então a ordenação é o fator dominante. Se as atividades já estiverem ordenadas pelo horário de término, somente a etapa gulosa resolve o problema em O(n) de tempo e O(1) de espaço extra.
O que é o problema das N reuniões em uma sala?
É o mesmo problema contado com reuniões: uma sala, N reuniões, e uma reunião só pode começar depois que a anterior terminar. Ordene as reuniões pelo horário de término e escolha cada uma que comece depois que terminar a última escolhida. Para listar as reuniões, registre cada índice escolhido, desempantando horários de término iguais pelo menor índice.
O problema de seleção de atividades é de programação dinâmica?
Pode ser, mas não precisa. Uma tabela com as atividades ordenadas pelo horário de término, contendo o maior número de atividades que terminam com cada uma delas, fornece a resposta em O(n²). A escolha gulosa é sempre segura, então uma única passada é suficiente. A tabela se torna a ferramenta certa quando as atividades têm valores e você maximiza o total deles.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def maxActivities(start, finish):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
start = [10, 12, 20, 14, 25, 21] finish = [13, 16, 24, 19, 30, 22]
Saída Esperada
4