Given a collection of intervals, merge all overlapping intervals.

Example 1:


Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].


Example 2:


Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.

Difficulty: interview

Starter code:

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        

Solutions:
# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def merge(self, intervals):
       new_intervals = []
       for interval in sorted(intervals, key=lambda i: i.start):
         if new_intervals and interval.start <= new_intervals[-1].end:
           new_intervals[-1].end = max(new_intervals[-1].end, interval.end)
         else:
           new_intervals.append(interval)
       return new_intervals


# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def merge(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: List[Interval]
         """
         if len(intervals) < 2:
             return intervals
         intervals = sorted(intervals, key=lambda s: s.start)
         rs = []
         cur = intervals[0]
         for r in intervals[1:]:
             if r.start <= cur.end:
                 cur.end = max(r.end, cur.end)
             else:
                 rs.append(cur)
                 cur = r
         rs.append(cur)
         return rs
         

class Solution:
     def merge(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: List[Interval]
         """
         inters = sorted(intervals, key=lambda intval: intval.start)
         ret = []
         n = len(intervals)
         if n == 0:
             return ret
         s = inters[0].start
         e = inters[0].end
         for i in range(1, n):
             if inters[i].start <= e:
                 e = max(inters[i].end, e)
             else:
                 ret.append(Interval(s, e))
                 s = inters[i].start
                 e = inters[i].end
         ret.append(Interval(s,e))
         return ret

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def merge(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: List[Interval]
         """
         start = sorted([interval.start for interval in intervals])
         end = sorted([interval.end for interval in intervals])
         if not start:
             return end
         if not end:
             return start
         result = list()
         make_interval = 1
         i, j = 1, 0
         first_start = 0
         while i < len(start) and j < len(end):
             if start[i] <= end [j]:
                 make_interval += 1
                 i += 1
             else:
                 make_interval -= 1
                 if make_interval == 0:
                     result.append([start[first_start], end[j]])
                     first_start = i
                 j += 1
                     
         if j < len(end) :
             result.append([start[first_start], end[-1]])
         return result
                 

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def merge(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: List[Interval]
         """
         length=len(intervals)
         if length==1 or length==0: return intervals
         intervals.sort(key=lambda l:l.start)
         result=[]
         curr=intervals.pop(0)
         while intervals:
             next_int=intervals.pop(0)
             if curr.end>=next_int.start:
                 curr.end=max(next_int.end,curr.end)
             else:
                 result.append(curr)
                 curr=next_int
         result.append(curr)
         return result
     

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def merge(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: List[Interval]
         """
         length=len(intervals)
         if length==1 or length==0: return intervals
         intervals.sort(key=lambda l:l.start)
         result=[]
         curr=intervals.pop(0)
         while intervals:
             next_int=intervals.pop(0)
             if curr.end>=next_int.start:
                 if curr.end<next_int.end:
                     curr.end=next_int.end
             else:
                 result.append(curr)
                 curr=next_int
         result.append(curr)
         return result
     

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def merge(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: List[Interval]
         """
         if not intervals: return []
         intervals = sorted(intervals, key=lambda x: (x.start, x.end))
         res = [Interval(intervals[0].start, intervals[0].end), ]
         for i in range(1, len(intervals)):
             if intervals[i].start <= res[len(res) - 1].end:
                 res[len(res) - 1].start = min(res[len(res) - 1].start, intervals[i].start)
                 res[len(res) - 1].end = max(res[len(res) - 1].end, intervals[i].end)
             else:
                 res.append(Interval(intervals[i].start, intervals[i].end))
         return res

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def merge(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: List[Interval]
         """
         if not intervals:
             return []
         intervals.sort(key=lambda a: (a.start, a.end))
         ptr = 0
         while ptr < len(intervals) - 1:
             if intervals[ptr].end >= intervals[ptr+1].start:
                 p = intervals.pop(ptr + 1)
                 intervals[ptr].end = max(intervals[ptr].end, p.end)
             else:
                 ptr += 1
         
         return intervals

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def merge(self, intervals):
         si = sorted(intervals, key=lambda x: (x.start, x.end))
         cur = 1  # index of current tuple
         while cur < len(si):
             # check intersection of current and previous tuple
             # if end of previous is less than begin of current
             # there are the intersection, we should merge them
             # into the bigger interval
             if si[cur - 1].end >= si[cur].start:
                 # change end of the interval(tuple)
                 si[cur - 1] = Interval(si[cur - 1].start, max(si[cur - 1].end, si[cur].end))
                 # delete unnecessary interval(tuple)
                 del si[cur]
             # there are no intersection, go to the next tuple
             else:
                 cur += 1
         return si
         

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def merge(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: List[Interval]
         """
         '''
         先按照每个会议的开始时间排序，用一个数列来保存会议，条件是
         如果当前会议的开始时间比数列中最后一个会议的结束时间还晚，另起炉灶。
         如果开始时间比结束时间还早，挤进去！比较会议的结束时间，更新。
         '''
         intervals.sort(key=lambda x : x.start)
         res = []
         for interval in intervals:
             # 如果res 是空的，初始化的情况，要把第一个会议加进去！
             if not res or interval.start > res[-1].end:
                 res.append(interval)
             else:
                 res[-1].end = max(interval.end, res[-1].end)
         return res
         

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def merge(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: List[Interval]
         """
         length=len(intervals)
         if length==1 or length==0: return intervals
         intervals.sort(key=lambda l:l.start)
         index=0
         while index<len(intervals)-1:
             curr=intervals[index]
             if curr.end>=intervals[index+1].start:
                 intervals.pop(index)
                 next_int=intervals.pop(index)
                 if curr.end<next_int.end:
                     curr.end=next_int.end
                 intervals.insert(index,curr)
             else:
                 index+=1
         return intervals