[Leetcode 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.

 

Example 1:

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

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

 

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

1.  intervals를 start를 기준으로 sorting (end도 sorting의 두 번째 인자로 넣어도 되지만 어차피 merging할 수 있는 interval들 중 제일 멀리 있는 끝지점으로 업데이트 할 것이기 때문에 안해도 상관없다)
2. 현재 interval과 다음 interval의 범위를 보고, 이걸 merging할 것인지 새로운 interval로 볼 것인지 판단하며 모든 interval을 확인

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: (x[0]))
        left_cursor, right_cursor = intervals[0][0], intervals[0][1]
        answer = []
        for interval in intervals:
            start = interval[0]
            end = interval[1]
            if start <= right_cursor:
                right_cursor = max(right_cursor, end)
            else:
                answer.append([left_cursor, right_cursor])
                left_cursor = start
                right_cursor = end
        answer.append([left_cursor, right_cursor])
        return answer

다른 사람들 풀이를 보다가 저렇게 cursor로 안하고 interval 자체를 수정해서 넣는 사람이 있길래 따라해봤다.

 

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: (x[0]))
        answer = []
        new_interval = intervals[0]
        for interval in intervals:
            start = interval[0]
            end = interval[1]
            if start <= new_interval[1]:
                new_interval[1] = max(new_interval[1], end)
            else:
                answer.append(new_interval)
                new_interval = interval
        answer.append(new_interval)
        return answer

메모리는 조금 덜 쓰는데 런타임은 좀 더 걸린다.. 

 

참고 사이트

https://kyungseop.tistory.com/13

[LeetCode] 56. Merge Intervals

정렬하고 나서 첫번째 interval을 일단 넣길래 end가 더 길면 어떻게 하려고 저러지 하고 가만히 뜯어보니까 java는 배열이 reference variable이라서 나중에 업데이트 해도 상관이 없다. 새로운 배열을 할당해서 그걸 리턴할 리스트에 추가하는 게 아니라 주어진 interval을 가리키게 하고 interval의 값 자체를 업데이트 한다. 오호오라

 

이거 보고 Python에는 pointer가 없다, C에서 pointer를 이용해 value를 넘기는 방식과 유사하게 동작하는 거다 라는 말이 생각났다. 

https://rroundtable.github.io/FastPages/python/pointer/2019/08/03/Python-%EB%B3%80%EC%88%98%ED%95%A0%EB%8B%B9%EC%9D%98-%EA%B0%9C%EB%85%90.html

“Python 변수할당의 개념”

https://brownbears.tistory.com/519

[Java] 참조 타입과 참조 변수

https://sorjfkrh5078.tistory.com/278

[Java] Java에 포인터가 없는 이유 - 포인터(Pointer) vs 참조(Reference)