Central de atendimento

Uma central tem $K$ servidores, numerados de 1 a $K$. O servidor $j$ executa $v_j$ unidades de trabalho por unidade de tempo. Todos começam livres no instante 0.

Há $N$ solicitações, numeradas de 1 a $N$ na ordem em que aparecem na entrada. A solicitação $i$ chega no instante $a_i$, tem prioridade $p_i$ (quanto menor, mais prioritária), exige unidades de trabalho, só pode ser iniciada até o instante e informa quais servidores podem atendê-la. Se iniciar no servidor no instante , termina em

$$t+\left\lceil\frac{w_i}{v_j}\right\rceil.$$

Um atendimento não é interrompido. Pode terminar depois de $b_i$: esse limite vale somente para o início.

Em cada instante em que chega alguma solicitação ou termina algum atendimento, aplique estas etapas:

1. Libere todos os servidores que terminam nesse instante e acrescente todas as solicitações que chegam nesse instante à espera.
2. Considere os servidores livres em ordem crescente de identificador. Para cada um, escolha entre as solicitações ainda esperando que ele pode atender e cujo prazo de início não expirou. Escolha a menor tripla $(p_i,a_i,i)$ em ordem lexicográfica: menor prioridade numérica, depois chegada mais antiga, depois menor identificador. Comece imediatamente esse atendimento. Uma solicitação escolhida deixa de estar disponível para os próximos servidores.

Um servidor sem solicitação elegível continua livre. Solicitações cujo prazo passa enquanto esperam nunca serão atendidas. Determine o servidor e o instante de término de cada solicitação, ou informe que ela não foi atendida. A entrada não precisa estar ordenada por chegada.

4 2
1 2
0 0 2 4 11
0 0 1 4 11
2 2 1 2 10
2 3 1 2 01

2 2
1 4
0 -1
2 3