Escalonamento de intervalos com pesos

• Cada tarefa j tem um início $s_j$ e um fim $f_j$ e tem um peso ou valor $v_j$.
• Duas tarefas são compatíveis se elas não se sobrepõem 
• Meta: encontrar o subconjunto de tarefas mutuamente compatíveis com maior peso.

Figura retirada dos slides  http://www.cs.washington.edu/education/courses/cse417/08wi/notes/11-dp-sched-complete.pdf

O algoritmo guloso funciona para esse problema quando todas as tarefas tem o mesmo peso.

1. Ordene as tarefas em ordem crescente de tempo final.

2. Adicione um tarefa no subconjunto construído se ela é compatível quando as tarefas previamente escolhidas. Note que para executar este passo basta comparar o início da tarefa com o final da última tarefa escolhida.

Note que esta estratégia não funciona quando os pesos não são iguais.

O algoritmo guloso falha quando ordenamos por tempo final ou ordenamos por peso.

Contra-exemplo 1: ordenando por tempo final

Contra-exemplo 2: ordenando por peso

Programação Dinâmica

Ordene as tarefas pode ordem de tempo final: $f_1$,$f_2$,$f_3$,....

Defina p(j) = maior indíce i < j tal que a tarefa i é compatível com a tarefa j.

typedef struct{
  int s,f,w;
} tarefa;

tarefa t[MAXN];
int p[MAXN];

int order_by_finish(const void *a, const void *b){
  tarefa pa,pb;

  pa = *(tarefa *)a;
  pb = *(tarefa *)b;

  return pa.f - pb.f;
}

Agora, vamos decompor o problema definindo uma estrutura recursiva. A forma de decompor será chamada de escolha binária. A escolha binária também é utilizada no problema da mochila.

OPT(j) = valor da solução ótima do problema consistindo das tarefas 1,2,..,j.

Note que temos que avaliar dois casos:

• Se a tarefa j é escolhida então não podemos usar nenhuma tarefa que  incompatível com j. Logo, p(j) entra em acão. As tarefas {p(j)+1,...,j-1} serão descartadas, o problema fica:

OPT(j) = OPT(p(j)) + v(j)

• Se a tarefa j não é escolhida então o problema é reduzido para 

OPT(j) = OPT(j-1).

Logo, a solução é dada por 

OPT(j) = max(OPT(p(j)) + v(j), OPT(j-1)).

Main

t[0].s = 0;
t[0].f = 0;
t[0].w = 0;

for(i=1;i<=n;i++)
   scanf("%d %d %d",&t[i].s,&t[i].f,&t[i].w);

qsort(t,n+1,sizeof(tarefa), order_by_finish);

for(i=1;i<=n;i++){
   p[i] = 0;
   for(j=i-1;j>=1;j--){
      if(t[j].f <= t[i].s){
          p[i] = j;
          break;
      }
   }
}

opt[0] = 0;
for(j=1;j<=n;j++){
  opt[j] = max(opt[j-1], opt[ p[j]] + t[j].w);     
}
printf("%d\n",opt[n]);

SPOJ:

http://www.spoj.com/problems/RENT/

Referência:

http://www.cs.washington.edu/education/courses/cse417/08wi/notes/11-dp-sched-complete.pdf