56. Merge Intervals

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.

My Answer 1: Accepted (Runtime: 92 ms - 28.57% / Memory Usage: 16.2 MB - 9.17%)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        result = []
        
        for i in range(len(intervals)):
            if intervals[i][0] == -1:
                continue
                
            for j in range(i+1, len(intervals)):
                if intervals[j][0] == -1:
                    continue
                
                if intervals[i][0] <= intervals[j][0] and intervals[j][0] <= intervals[i][1]:
                    intervals[i][1] = max(intervals[i][1], intervals[j][1])
                    intervals[j][0] = -1
        
        for i in range(len(intervals)):
            if intervals[i][0] != -1:
                result.append(intervals[i])
        
        return result

intervals 를 순서대로 정렬한 후,
intervals[i] 범위에 속하는 intervals[j] 값이 있으면 i 로 포함시킴
범위가 커져야 하는 경우는 intervals[i][1] 값을 intervals[j][1] 로 늘려줌
포함된 intervals[j] 의 [0] 값은 -1 로 바꿔준다.

맨 마지막에 [0] 이 -1 값이 아닌 값들만 result 에 넣어주고 리턴

일단 sort 로 정렬부터가 비효율인거 같았는데 은근 많이 쓰는듯..?

Sorting

Solution 1: Runtime: 140 ms - 5.34% / Memory Usage: 16.2 MB - 42.67%

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

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

        merged = []
        for interval in intervals:
            # if the list of merged intervals is empty or if the current
            # interval does not overlap with the previous, simply append it.
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
            # otherwise, there is overlap, so we merge the current and previous
            # intervals.
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

솔루션에도 sorting 이 있다