EPI Python 13.8 compute the union of intervals

#1 
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

I am having a really hard time why my program isn’t passing the python EPI judge. When I was going through the debugger, my program doesn’t merge the endpoints “(176, False, 183, False), (183, True, 192, True)” , but when I hard coded the actually endpoint objects and tried to merge them using the same logic in my code ie:“don’t merge if and only if the previous right endpoint and the current left endpoint are both False” assuming these points have equal val values.

0 Likes