CountOlaf's blog

Job Scheduling POI
By CountOlaf, history, 8 years ago, In English

I was trying this problem for quite a while, but failed to come up with the correct solution. Maybe you guys can help me.

Problem link: http://main.edu.pl/en/archive/oi/2/sze

Tags poi
  • Vote: I like it
  • +18
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 3   Vote: I like it +21 Vote: I do not like it

Think about some job i, i+1. The total time to complete job i+1 (in order of [1 ... i-1] [i] [i+1]) is

T + aiT + bi + ai + 1(T + aiT + bi) + bi + 1

 = (ai + 1 + 1)((ai + 1)T + bi) + bi + 1

when T =  total time took to complete till job i-1

now think that we process in order of [1 ... i-1] [i+1] [i], then the total time is

(ai + 1)((ai + 1 + 1)T + bi + 1) + bi

Say ci = ai + 1. now, if this inequality holds, it's better to swap job i and i+1.

ci + 1ciT + ci + 1bi + bi + 1 > cici + 1T + cibi + 1 + bi

which is

ci + 1bi + bi + 1 > cibi + 1 + bi

now replace ci to ai, we get :

ai + 1bi > bi + 1ai

So, if above equality holds, we should swap i and i+1. This is essentially angular sort.

code : http://ideone.com/c70x8s

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Thanks a lot. That's a really nice solution :)

    → Reply