-
May 23rd, 2013, 04:48 AM
#1
Algorithm for finding subset of permutations with maximum value
Hello,
Can anyone help with suggestions for implementation of an efficient algorithm for the following issue:
Given a list of permutations with a score for each permutation, we need to find a subset of permutations with the highest summed score, given the condition that any one of permutation in the subset will not intersect or be contained with another permutation in the subset.
For example, given the following list of permutations, marked as |Index: start, end, score|, permutation A cannot be in the same subset with permutation B, since they intersect with each other. Permutation C cannot be in the same subset with permutation F, since permutation F is contained within permutation C.
A: 43 70 27
B: 45 74 26
C: 3 28 24
D: 65 99 45
E: 20 39 26
F: 10 18 20
G: 78 97 23
I guess the challenge is to implelent this in O(NlogN) rather than the naïve implemention of O(N2)
Thanks in advance!
Tom.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
On-Demand Webinars (sponsored)
|