7 lines, easy, Python


  • 60

    Just go through the intervals sorted by start coordinate and either combine the current interval with the previous one if they overlap, or add it to the output by itself if they don't.

    def merge(self, intervals):
        out = []
        for i in sorted(intervals, key=lambda i: i.start):
            if out and i.start <= out[-1].end:
                out[-1].end = max(out[-1].end, i.end)
            else:
                out += i,
        return out

  • 0
    C
    This post is deleted!

  • -2
    C

    Very nice and concise solution!

    My solution uses a similar concept (sort the starts and then iterate over the sorted array) but its longer than yours. The only (if any) advantage of my solution is that mine does not mutate the input Interval objects.

    def merge(self, intervals):
        if not intervals:
            return []
        int_sort = sorted(intervals, key=lambda x: x.start)
        ans, start, end = [], int_sort[0].start, int_sort[0].end
        for n in int_sort[1:]:
            if n.start > end:
                ans.append(Interval(start, end))
                start, end = n.start, n.end
            else:
                end = max(end, n.end)
        ans.append(Interval(start, end))
        return ans

  • 2
    S

    Thanks for sharing! About 'out += i,' it is similar to out.append(i), but why it works in python?


  • 3

    Yes, it has the same effect as that append. The i, is a tuple (because of the comma), and you can += a tuple to a list.


  • 0
    S

    Thanks, it is very helpful!


  • 0
    S

    Why this ‘+=’ works for adding a tuple to a list? I can only add list to list, yes? I try: list = [1, 2], list = list + (3, 4)
    TypeError: can only concatenate list (not "tuple") to list


  • 0

    Yes, with + you can only add a list, but with += I think you can add any iterable. Not sure why they did that. Maybe because a += b modifies the existing a so it's clear what to do but in a + b it's not clear what you want if they're different types.


  • 0

    Just found a good answer.


  • 0

    this is a fantastic, readable, and concise solution. Mine went excessively longer than yours although it was a similar concept. Thanks for sharing.


  • -1
    M

    if out and i.start <= out[-1].end:
    what is "if out "means? I mean if out is in intervals? I don't really get this part. Thank you.


  • 0
    M

    And Also, why it doesn't work without the comma after out += i? I understand += and out = out +i, but I don't get the , part. Thank you.


  • 0

    Since out is a list, if out means "if out isn't empty".
    The comma has already been discussed in the previous comments, have you read them?


  • -1
    N
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        intervals.sort(lambda a,b: a.end - b.end)
        intervals.sort(lambda a,b: a.start - b.start)
        i, n = 0, len(intervals)
        result = []
        while i < n:
            s = i
            j = i + 1
            maxEnd = intervals[i].end
            while j < n and maxEnd >= intervals[j].start:
                maxEnd = max(maxEnd, intervals[j].end)
                i += 1
                j += 1
            result.append(Interval(intervals[s].start, maxEnd))
            i = j
        return result
    

  • 0

    This one is not only short but also saving space and no extra variables.


  • 0
    Y
    This post is deleted!

  • 0

    This is really cool solution, I have a similar solution but use more space...

    class Solution(object):
        def merge(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: List[Interval]
            """
            if len(intervals)<2:
                return intervals       
            res = []
            intervals.sort(key = lambda x: x.start)
            temp = intervals[0]
            for i in range(1, len(intervals)):
                if intervals[i].start <= temp.end:
                    temp.end = max(temp.end, intervals[i].end)
                else:
                    res.append(temp)
                    temp = intervals[i]
            res.append(temp)
            return res
    

  • 0
    L
    This post is deleted!

  • 0
    L
    This post is deleted!

  • 0

    @lightning_mi Uh... you call it in-place and the first thing you do is create a copy? Also I don't see what this has to do with mine, i.e., why you posted it here...


Log in to reply
 

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