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
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
def merge(self, intervals): if not intervals: return  int_sort = sorted(intervals, key=lambda x: x.start) ans, start, end = , int_sort.start, int_sort.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
Thanks for sharing! About 'out += i,' it is similar to out.append(i), but why it works in python?
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.
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
+ 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.
Just found a good answer.
this is a fantastic, readable, and concise solution. Mine went excessively longer than yours although it was a similar concept. Thanks for sharing.
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.
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.
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?
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
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 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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.