Last active
June 23, 2017 00:23
-
-
Save mynameisfiber/2495ac764a7839fcda2a34c3cfd73446 to your computer and use it in GitHub Desktop.
Solve for the largest number of lists of intervals such that no intervals intersect.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from operator import itemgetter | |
def area(items): | |
return len(items) * sum(i[1] - i[0] for i in items) | |
def mutually_exclusive_list_list_intervals(data): | |
""" | |
Data is list of lists of intervals. We'd like to keep the most number of | |
high level lists such that none of the intervals intersect. | |
This is an approximate, greedy, solution that guarentees no intersection | |
but may not be the optimal solution. It runs at O(n logn) so that's not | |
bad. | |
""" | |
data_expanded = [(*d, area(items), i) | |
for i, items in enumerate(data) | |
for d in items] | |
data_expanded.sort(key=lambda item: item[0]) | |
to_remove = set() | |
i = 0 | |
de = data_expanded | |
while i < len(de) - 1: | |
# make sure current element is not marked for deletion | |
if de[i][4] not in to_remove: | |
# now we make sure the next item to compare against isn't marked | |
# for deletion | |
j = i + 1 | |
try: | |
while de[j][4] in to_remove: | |
j += 1 | |
except IndexError: | |
break | |
# check if this endpoint is after the next items start | |
if de[i][1] > de[j][0]: | |
this_area = de[i][3] | |
next_area = de[j][3] | |
# pick the item with the least "area" in terms of the higher | |
# order list of intervals. This is a heuristic to remove long | |
# lists of small intervals. We want those out because they have | |
# a higher probability of intersecting with many other lists of | |
# intervals. | |
if this_area < next_area: | |
to_remove.add(de[j][4]) | |
else: | |
to_remove.add(de[i][4]) | |
i -= 1 | |
i += 1 | |
return [d for i, d in enumerate(data) if i not in to_remove] | |
data = [ | |
[(1, 5, 'a')], | |
[(6, 9, 'b')], | |
[(8, 20, 'c')], | |
[(7, 8, 'a'), (9, 10, 'c')], | |
] | |
print(data) | |
print(mutually_exclusive_list_list_intervals(data)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment