PDA

Pogčedajte punu verziju : rasporedjivanje osoba po vremenskom rasporedu (?)


cvele
10. 03. 2011., 09:53
Postoji X ucenika i 1 profesor. Svaki od ucenika ima vremenski interval u kome je slobodan da uzme cas (startTime i endTime). Profesor radi od profesorStartTime do profesorEndTime.
Treba napisati fju koja ce umeti da rasporedi sve ucenike (njih X) u vremenskom intervalu profesorStartTime - profesorEndTime uzimajuci u obzir kada je koji ucenik slobodan. Nijedan vremenski uslov(interval) nesme biti prekrsen. Ukoliko nije moguce napraviti raspored, treba da vrati false.

Uh tako nekako :) nije tolko bitan programski jezik, ko ovo uspe da mi resi ima pragnje u Nisu ili Palicu ove godine.

cvele
10. 03. 2011., 09:57
Da dodam duzina casa je N, odnosno svaki put kad se pozove fja dodeljuje se nova duzina casa.

nn.nn
10. 03. 2011., 10:40
Ovo verovatno neće biti odgovor kome se nadaš, ali možda pomogne:

http://www.unitime.org/

http://muller.unitime.org/

Na prvom linku je open source aplikacija za pravljenje rasporeda, a na drugom imaš i neke radove koji se bave teorijskom (ima, čini mi se, i nekakvog koda u njima) stranom problema.

jablan
10. 03. 2011., 12:27
Jel svaki učenik treba da dobije tačno po jedan čas?

jablan
10. 03. 2011., 13:14
Ako ti nisu bitne performanse, uvek ostaje brute force:



# trazi redosled ucenika za koji je moguce napraviti raspored
def rasporedi ucenici, profa, cas
ucenici.keys.permutation.map{|redosled|
poredjaj ucenici, profa, cas, redosled
}.find{|e| e}
end

# za zadati redosled ucenika, odredjuje pocetak i kraj casa
def poredjaj ucenici, profa, cas, redosled
poc = profa.first
redosled.inject({}) do |acc, ime|
poc = [ucenici[ime].first, poc].max
return nil if poc+cas > [profa.last, ucenici[ime].last].min
acc[ime] = [poc, poc+cas]
poc += cas
acc
end
end

ucenici = {
pera: [6,8], # slobodan od 6 do 8
zika: [2,5], # slobodan od 2 do 5
mika: [1,3] # slobodan od 1 do 3
}

profa = [1,8] # slobodan od 1 do 8

p rasporedi ucenici, profa, 1
#=> {:mika=>[1, 2], :zika=>[2, 3], :pera=>[6, 7]}

p rasporedi ucenici, profa, 2
#=> {:mika=>[1, 3], :zika=>[3, 5], :pera=>[6, 8]}

cvele
10. 03. 2011., 15:11
Dakle, jablane ne samo pragnje nego i pivo da speres :)

ivanhoe
10. 03. 2011., 15:52
to bi trebalo da je jedan od ovih problema http://en.wikipedia.org/wiki/Dynamic_programming

miloshz
16. 07. 2011., 18:55
prvo gledas da li je profesor zauzet, zatim definises array ucenika pa gledas ucenik[n]=false i onda mu dodelis timeslot

problem zaista deluje simple i cudi me da programer tvog kalibra nije mogao resiti

DejanVesic
31. 07. 2011., 13:56
@miloshz :-) :-) :-) :-)

Hajde probaj da ga optimalno rešiš :-)