rasporedjivanje osoba po vremenskom rasporedu (?)

[cvele]

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]

Da dodam duzina casa je N, odnosno svaki put kad se pozove fja dodeljuje se nova duzina casa.

[nn.nn]

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]

Jel svaki učenik treba da dobije tačno po jedan čas?

[jablan]

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]

Dakle, jablane ne samo pragnje nego i pivo da speres

[ivanhoe]

to bi trebalo da je jedan od ovih problema http://en.wikipedia.org/wiki/Dynamic_programming

[miloshz]

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]

@miloshz :-) :-) :-) :-)

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