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\$

closed as off-topic by Daniel, Mast, yuri, Ben Steffan, t3chb0t Jul 30 '18 at 7:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – Daniel, Mast, yuri, Ben Steffan, t3chb0t
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\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 '17 at 10:20
  • \$\begingroup\$ @Coal_, problem with AttributeError is PEP 3113 and python version diffrence \$\endgroup\$ – vaeta Dec 30 '17 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 '17 at 22:59
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.