qweer pisze:
>> Najprostsze, choć może lekko nieoptymalne pamięciowo(przyjmuję założenie
>> o jednostkowym rozmiarze zadania): Robisz graf skierowany w którym w
>> węzłach masz licznik - na ile zadań dane zadanie czeka bezpośrednio oraz
>> listę zadań które czekają na nie (odwrotnie niż w danych wejściowych).
>> Przeglądasz dane 1 raz i do listy wrzucasz wszystkie zadania z
>> licznikiem=0 - to jest 1 grupa. ->Dopóki są jakieś zadania na tej
>> liście. Wypisz grupę, odejmij 1 od liczników każdego zadania na które
>> wskazują te z listy dodając do drugiej listy te którym licznik się
>> wyzerował. Wywal pierwszą listę. Aktualną listą jest 2 lista. Powtórz
>> ->. Jeżeli w grafie zostały zadania z niezerowym licznikiem to znaczy,
>> że był cykl.
>
> Tak, tak, ale nie mam tutaj ograniczen czasowych.
Hm? nie zrozumiałem... Jeżeli nie masz ograniczeń czasowych (czyli każde
zadanie ma jednostkowy czas i nie ma linii krytycznych(one akurat nie
mają sensu przy nieskończonej ilości procesorów)) to to co napisałem
jest ok.

co: na co czeka
1:2,3
2:
3:4,2
4:

dostajesz 3 sestawy:
2,4
3
1
> Jezeli byloby tak, to bym mogl tutaj wykorzystac
> lekko zmodyfikowany algorytm wyznaczania sceizki krytycznej (juz nie pamietam
> kogo to byl wynalazek)
Jeżeli masz określone różne długości zadań to zamieniasz listę na listę
posortowaną wg długości (set) i zawsze zdejmujesz (wszystkie)
najkrótsze, uaktualniasz wskazywane przez nie, jeżeli wyjdzie jakieś 0
to dorzucasz do seta. Pracujesz póki set jest niepusty. A kolejny zestaw
się pojawia zawsze gdy jakieś zadanie z seta wywaliłeś.

(długość)
1(1):2,3
2(4):
3(2):4,2
4(1):
5(2):4
dostajesz (ile się grupa wykonuje):
2,4 (1)
2,5 (2)
2 (1)
3 (2)
1 (1)

--
Pozdrawiam
Michoo