5
\$\begingroup\$

Given a collection of intervals, merge all overlapping intervals.

input: [1,3],[2,6],[8,10],[15,18],

output: [1,6],[8,10],[15,18].

The logic is very simple: just merge all the intervals iteratively from first to last.

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
        def merge(self, intervals_struct):
            """
            :type intervals: List[Interval]
            :rtype: List[Interval]
            """
            def is_intersect((i1_l, i1_r), (i2_l, i2_r)):
                if i1_r >= i2_l and i1_r <= i2_r:
                    return True
                elif i2_r >= i1_l and i2_r <= i1_r:
                    return True
                return False

            def merge_interval((i1_l, i1_r), (i2_l, i2_r)):
                return [min(i1_l, i2_l), max(i1_r, i2_r)]

            intervals = []
            for i in intervals_struct:
                intervals.append([i.start, i.end])

            intervals = sorted(intervals, key=lambda x:x[0])

            i, result = 0, []
            while i < len(intervals):
                max_l, max_r = intervals[i] 
                while i < len(intervals) and is_intersect([max_l, max_r], intervals[i]):
                    max_l, max_r = merge_interval([max_l, max_r], intervals[i])
                    i += 1
                result.append([max_l, max_r])
                if i < len(intervals) and intervals[i] == [max_l, max_r]:
                    i += 1
            return result
\$\endgroup\$
3
  • \$\begingroup\$ There's at least two syntax errors and an AttributeError being thrown. Are you sure you meant to comment out the Interval class definition? \$\endgroup\$
    – Daniel
    Dec 29, 2017 at 10:20
  • \$\begingroup\$ @Coal_, problem with AttributeError is PEP 3113 and python version diffrence \$\endgroup\$
    – vaeta
    Dec 30, 2017 at 20:30
  • \$\begingroup\$ No, the AttributeError's to do with the fact that you commented out the Interval class definition. \$\endgroup\$
    – Daniel
    Dec 30, 2017 at 22:59

1 Answer 1

3
\$\begingroup\$

Python2 / Python3

Your code don't working under python 3 (PEP 3113). If possible better use newer python :).

Algorithm

  • no needs to change Interval to list with two elements. It's bad practise. You try low-level optimizations, not algorithm one. Code is less readable.
  • local functions is_intersect and merge_interval don't use knowledge that we have sorted intervals, e.g. i1_l <= i2_l
  • pattern while i < len(my_list): better change to for element in my_list: because we don't need index

Reduced code

class Interval(object):
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e


class Solution(object):
    def merge(self, intervals_struct):
        if not intervals_struct:
            return []
        intervals = sorted(intervals_struct, key=lambda x: x.start)

        result = [intervals[0]]
        for cur in intervals:
            if cur.start > result[-1].end:
                result.append(cur)
            elif result[-1].end < cur.end:
                result[-1].end = cur.end
        return result
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.