Triagem de empréstimo: ordenando uma fila de tarefas
Por que isso importa "Use uma priority queue" é o reflexo para qualquer fila com prioridades. Ela responde "quem importa mais?" quando a pergunta real é frequentemente "quem pode esperar menos?". Outros campos têm respondido a essa pergunta por muito tempo.
Três mesas
A emergência de um hospital. Uma enfermeira de triagem coloca cada chegada em uma categoria, e cada categoria tem um tempo alvo para ser atendida: no sistema Manchester amplamente usado, imediatamente, em 10 minutos, 60, 120 ou 240. Quando um médico fica livre, o próximo paciente não é simplesmente o mais doente na sala: um paciente padrão prestes a ultrapassar seu alvo pode passar antes de um urgente que chegou há um minuto e ainda tem tempo.
Check-in de aeroporto. Existem filas separadas para premium e econômica. Dentro de uma fila, as pessoas são atendidas por ordem de chegada. Mas quando um voo está prestes a fechar, os funcionários percorrem a fila da econômica chamando aquele voo para frente, antes dos passageiros premium cujos voos saem mais tarde.
A biblioteca retorna desk. Uma linha, servida estritamente em ordem. Ninguém é ultrapassado, e a urgência de ninguém é considerada.
Compare antes de codar
- Em cada mesa, o que decide quem é atendido a seguir?
- Quais desks podem fazer alguém esperar para sempre? Quais podem fazer um caso urgente esperar demais?
- O hospital e o aeroporto não se parecem em nada. O que eles têm em comum? Escreva isso em uma frase que não mencione nem hospitais nem aviões.
- No aeroporto, por que basta olhar para a frente de cada fila?
O alvo
O sistema de tarefas em segundo planoA roda em um worker que leva exatamente um minuto por tarefa. As tarefas são interativas (prioridade 1), padrão (2) ou em lote (3), e cada prioridade tem uma promessa de serviço: o tempo máximo que uma tarefa daquela prioridade pode esperar antes de começar. O agendador atual sempre executa a tarefa de maior prioridade que está esperando, e as tarefas em lote perdem sua promessa toda tarde.
Escreva order(jobs, max_wait). jobs é uma lista de {"id", "arrive", "priority"} ordenados por arrive (minutos inteiros); max_wait mapeia prioridade para o máximo de minutos que um trabalho pode esperar. Retorne os ids dos trabalhos na ordem que o worker os executa. O worker executa um trabalho por minuto: um trabalho começa no momento mais tardio entre sua chegada e o fim do trabalho anterior, e sua espera é o início menos a chegada. Rule: nenhum trabalho pode esperar mais que max_wait[priority]. Os dias de teste podem todos ser atendidos sem nenhum trabalho atrasado; com {1: 3, 2: 20, 3: 60} um dia tem cerca de 1,000 trabalhos.
Viu um problema nesta lição? Reporte-o · Pergunte sobre esta lição
Este exercício abre em breve
Termine a lição anterior para que esta seja desbloqueada. O curso inteiro é gratuito, não precisa de conta, e você pode ler esta lição agora mesmo.
Este navegador está bloqueando cookies para learn.floati.life, então as lições que você terminou aqui não podem abrir em ordem. Permita cookies para este site e recarregue.