Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
- 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))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement