Вычислить объединение интервалов Элементы программирования Интервью 13.8 Python

Question

Моя программа должна вывести список объектов интервалов, выраженных в виде набора непересекающихся интервалов. Предположим, что True подразумевает закрытый конец, т.е.: включительно, а False подразумевает, что конечная точка является открытым, то есть: исключительный. Например, рассмотрим пример «(176, False, 183, False), (183, True, 192, True)». Первая пара в каждом кортеже относится к левой конечной точке, 2-я относится к правой конечной точке. Если это были единственные интервалы в интервалах параметров, вы должны вывести интервал с открытой левой конечной точкой 176 и закрытой правой конечной точкой 192. Однако, если вы измените левую конечную точку 2-го интервала на False, т.е. я должен вывести интервалы такими, какие они есть, поскольку они уже являются непересекающимися интервалами.

import collections
import functools

from test_framework import generic_test
from test_framework.test_utils import enable_executor_hook

Endpoint = collections.namedtuple('Endpoint', ('is_closed', 'val'))

Interval = collections.namedtuple('Interval', ('left', 'right'))


def union_of_intervals(intervals):
    """
    list of intervals, each interval object has left or right attribute, which is an endpoint object, which hs is_closed
    bool and val attributes
    :param intervals:
    :return:
    """
    # TODO - you fill in here.
    if not intervals: return []
    #sort based on leftmost startpoint
    intervals.sort(key=lambda x:x.left.val)
    res =[]
    for i in range(1,len(intervals)):
        prev = intervals[i-1]
        curr = intervals[i]
        if curr.left.val <prev.right.val:
            #merge
            new = Interval(min([prev.left,curr.left],key=lambda x:(x.val,not x.is_closed)),max([prev.right,curr.right],
                                                                                               key=lambda x:(x.val, x.is_closed)))
            intervals[i] = new
        elif curr.left.val == prev.right.val:
            if not curr.left.is_closed and not prev.right.is_closed:
                res.append(intervals[i - 1])
            else:
                #all True
                new = Interval(min([prev.left, curr.left], key=lambda x: (x.val, not x.is_closed)),
                               max([prev.right, curr.right],
                                   key=lambda x: (x.val, x.is_closed)))
                intervals[i] = new
        else:
            #left of current is greater than right of prev
            res.append(intervals[i - 1])
    res.append(intervals[-1])
    return res

У меня действительно тяжелое время, почему моя программа не проходит все тестовые случаи, особенно в наборе тестов EPI. Когда я проходил через отладчик, моя программа не объединяла конечные точки «(176, False, 183, False), (183, True, 192, True)», но когда я жестко закодировал фактически объекты конечной точки и попыталсяобъединить их, используя ту же логику в моем коде, то есть: «не объединять, если и только если предыдущая правая конечная точка и текущая левая конечная точка оба являются ложными», предполагая, что эти точки имеют равные значения val, это сработало, как предполагалось. Я обнаружил, что если я также добавлю второй параметр сортировки при первой сортировке списка интервалов, например:

intervals.sort(key=lambda x:(x.left.val,not x.left.is_closed))

, моя программа будет работать так, как задумано, и пройдет все тесты. В настоящее время я думаю, что это не имеет значения, поскольку я уже позаботился о том, является ли конечная точка закрытой или открытой конечной точкой в ​​моем решении? Любая помощь будет принята с благодарностью