How about dynamic programming solution to this problem?
The nth entry may be chosen or may not be chosen. If it is chosen then
the sub problem to be solved is that of all those entries whose start
times are after the end time of the nth entry.
C(N,S) = 1+C(N',S') where S' = S U {n} and N' = those members of N
whose start time is after the end time of nth entry.
Originally, S is empty and N = { 1, 2, ..., n }
if nth entry is not considered, then we need to find all such edges
which overlap with nth entry and for each of those entries, we solve
the sub problem. Whichever gives the minimum result, that's the answer.
C(N,S) = 1 + min over p { C(N',S'), where N' = N - {n} - {p}, S' = S U
{p} } where 'p' is an entry which overlaps with nth entry.
So, if we make a table of n X 2^n whose columns are power set of
{1,2,...,N} and whose rows are 1,2,...n. and keep filling it row-wise.
Let me know your opinions.
SPX2 wrote:
> its actually called backtracking
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
