56. Merge Intervals

Desription:

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

 

'''
[1] solution)

idea::
find overlapping intervals and edit intervals

code::
non_overlapping=[]  # answer

intervals.sort(key=lambda x:x[0]) # sort

tmp=intervals[0]

for inter in intervals:
    if inter[0]>tmp[1]:
        interval=[tmp[0],tmp[1]]
        answer.append(interval)
        tmp[0]=inter[0]
        tmp[1]=inter[1]
    else:
        if inter[1]>tmp[1]:
            tmp[1]=inter[1]
non_overlapping.append(tmp)
return non_overlapping

-T/C: O(nlogn) # for sorting O(nlogn) + for one pass O(n), n == len(intervals)
-S/C: O(n)     # for answer O(n) + for tmp O(1)
'''

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        answer=[]
        
        intervals.sort(key=lambda x:x[0]);  # O(nlogn)
        
        tmp=intervals[0]
        
        for ele in intervals:
            
            if ele[0] > tmp[1]:
                interval=[tmp[0],tmp[1]]
                answer.append(interval)
                tmp[0]=ele[0]
                tmp[1]=ele[1]
                
            else:
                if ele[1]>tmp[1]:
                    tmp[1]=ele[1]
                else:
                    continue
        
        answer.append(tmp)
        return answer