6-line Python solution, mix all starts and ends then sort, check overlap

  • 0

    Sort all starts and ends. key = lambda x:(x[0], -x[1]) ensures (5, -1) will be in front of (5, 1). Then check overlapping.

    def merge(self, intervals):
        result, overlap, begin = [], 0, float('-inf')
        for x, y in sorted([(i.start, 1) for i in intervals] + [(i.end, -1) for i in intervals], key = lambda x:(x[0], -x[1])):
            if y == 1 and not overlap: begin = x
            if y == -1 and overlap == 1: result += Interval(begin, x),
            overlap += y
        return result

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.