There are some keywords in text and start/end position of their occurrences. Keywords may partially overlap e.g. "something" -> "something"/"some"/"thing": keywords_occurences = { "key_1": [(11, 59)], "key_2": [(24, 46), (301, 323), (1208, 1230), (1673, 1695)], "key_3": [(24, 56), (1208, 1240)], ... } I need to select one position for each keyword so they don't overlap, for this case solution is: key_1: 11-59 key_2: 301-323 (or 1673-1695, it does not matter) key_3: 1208-1240 If this could not be done, select maximum numbers of unique non-overlapping keys. Looks like a kind of "exact hitting set" problem, but I can't find algorithm description. Continue reading...
