May 23rd, 2013, 05:48 AM
Algorithm for finding subset of permutations with maximum value
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!
Tags for this Thread
Click Here to Expand Forum to Full Width