Boilerplate-kod, urk.

Försöker skita ur mig ett bevis på en algoritms optimalitet i algoritmerkursen. Som en del i beviset skriver jag om vår algoritm med matematisk notation. Jag önskar mig ibland en kompilator för ren matematik.

Jag menar jämför den matematiska definitionen

a(R,{}) = |R|
a(R,L) = { a (R ⋃ {e}, L ∖ {l})          , if ∀ek ∈ R. ek > s
         | a ((R ∖ {ek}) ⋃ {e}, L ∖ {l}) , if ∃ek ∈ R. ek ≤ s
  where l = (s,e) = an elem in L such that ∀(sk,ek)∈L. s ≤ sk

med vår klumpiga pseudokod:

type Time = Int            // for example seconds from the start of the day.
type Lecture = (Time,Time) // (Starttime, Endtime)
type Room = list

int classrooms(list lectures){
  sortByStarttime(lectures) //O(n log n)

  rooms = [] // list of endtimes in rooms

  foreach l in lectures {  
    added = False
    // r = endtime of the last "added" lecture to this room
    foreach r in rooms{  
      if (l.startTime > r){
        // replace the room r's endtime with new 
        // endtime. O(1) since in the middle of traversal
        r = l.endTime 
        added = True
        break;
      }
    }
    if not added {
      // add a new room with endtime = l.endTime to rooms
      rooms.add(l.endTime); 
    }
  }
  return length(rooms);
}