lectures.alex.balgavy.eu

Lecture notes from university.
git clone git://git.alex.balgavy.eu/lectures.alex.balgavy.eu.git
Log | Files | Refs | Submodules

Activity selection.md (724B)

      1 +++
      2 title = "Activity selection"
      3 +++
      4 
      5 # Activity selection
      6 
      7 ## Problem
      8 
      9 Given set of activities with start and finish time, schedule as many as possible so they do not collide.
     10 
     11 | i   | 1   | 2   | 3   | 4   | 5   | 6   |
     12 | --- | --- | --- | --- | --- | --- | --- |
     13 | si  | 1   | 3   | 2   | 3   | 6   | 3   |
     14 | fi  | 3   | 4   | 5   | 5   | 7   | 9   |
     15 
     16 ## Solution
     17 If ordered on finish time, choose activity with earliest finish time.
     18 If ordered on start time, choose activity with latest start time.
     19 
     20 here, solution is: { (1,3) , (3,4) , (6,7) }
     21 so activities {1, 2, 5}
     22 
     23 Use an iterative greedy algorithm that literally tries adding everything.
     24 
     25 ## Complexity
     26 ϴ(n). You just go through all items once and you’re done.