| Given the right approach, this is pretty straight-forward.
Consider a time T, and all the activities that are active at time T.
For each of these activities, maintain the 'maximum-size set of mutually
compatiable activities' in time that now has this activity active. Ditto
for having no activities now active.
This works because at any point in time, the only things of interest are:
which activity is active, and how many activities have been activated.
for i in {0..N} do N[i] <- 0 ! N[0] is a special counter for 'nothing active'
E <- {s(i),f(i)}, in sorted order
For each e in E do
if e is a 's' endpoint s(i) then
N[i] <- N[0] + 1 ! Add i as another mutually compatible activity
! (if nothing is now active)
else {e is a 'f' endpoint f(i)}
N[0] <- max(N[0], N[i]) ! If i were active, nothing is active now
Now, N[0] = the maximum number of mutually compatible activities
For the 'sorted order' above, if some s(i) = f(i), the f(i) comes first
(so that that activity finishes before the next one starts at that time).
There are a few ways to reconstruct the set of activities. One is to run
the above algorithm in reverse (after having run it forward).
M <- � ! Initialize to the empty set
For each e in E (in reverse order) do
if e is a 's' endpoint s(i) then
N[0] <- N[i] - 1 ! Forward: N[i] <- N[0] + 1
else {e is a 'f' endpoint f(i)}
if N[0] = N[i] ! Forward: N[0] <- max(N[0], N[i])
M <- M & i ! Add i to the set of activities
N[0] <- -1 ! Set to an unknown/bogus value
C'est tout!
Note: the definition in .0 says that if s(i)>=f(j) or s(j)> f(i), the activities
don't overlap. Switching variables: if s(i)> f(j) or s(j)>=f(i), the activities
don't overlap. Thus, it should say that the activities don't overlap if
(and only if) s(i)>=f(j) or s(j)>=f(i).
|