Solve for the largest number of lists of intervals such that no intervals intersect.

mutually_exclusive_list_list_intervals.py

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))