[LeetCode] 56. Merge Intervals

Link : https://leetcode.com/problems/merge-intervals/description/

문제 설명

Given an array of intervals where intervals[i] = [start<sub>i</sub>, end<sub>i</sub>], 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 <= 10<sup>4</sup>

• intervals[i].length == 2

• 0 <= start<sub>i</sub> <= end<sub>i</sub> <= 10<sup>4</sup>

문제 분석

문제 자체는 굉장히 단순합니다.

• 범위가 overlap되는 부분이 있다면 합친다

저는 이부분을 단순하게 만들기 위해서 순서를 생각했습니다

1. intervals를 앞 숫자를 기준으로 정렬

2. interval을 순차적으로 순회

   1. 만약 앞 interval이 없다면, answer에 넣기

   2. 만약 앞 interval이 있다면, overlap 확인

      1. overlap이라면? → 앞 interval에 병합

      2. overlap이 아니라면 → answer에 넣기

3. 정답 반환

사실 정렬을 제외하면 문제의 내용을 그대로 구현하는 형식이라서 별도의 생각을 할 필요가 없었습니다.

그래서 시간 복잡도를 계산해보면 다음과 같습니다

1. 순서 정렬 : O(n log n)

2. 순차 반복 : O(n)

최종 : O(n log n) + O(n) = O(n log n)

문제 해결

import kotlin.math.max
import kotlin.math.min

class Solution {
    fun merge(intervals: Array<IntArray>): Array<IntArray> {
        // 순서가 중요
        intervals.sortBy { it[0] }

        val answer = mutableListOf<IntArray>()

        for (cur in intervals) {
            // 저장된 값이 없는 경우 무조건 넣기
            if (answer.isEmpty()) {
                answer.add(cur)
                continue
            }

            val last = answer.last()
            // 곂치는 부분이 있으면 합치기
            if (isOverlap(last, cur)) {
                last[1] = max(cur[1], last[1])
                last[0] = min(cur[0], last[0])
            } else {// 곂치는 부분이 없으면 넣기
                answer.add(cur)
            }

        }
        return answer.toTypedArray()
    }

    fun isOverlap(u: IntArray, v: IntArray): Boolean = u[1] >= v[0]
}

느낀점

단순한 문제로 생각되지만 그림이나 순서를 잘 생각해야하는 문제여서 엣지 케이스를 어떻게 하면 모두 커버할 수 있는지 추가적인 생각이 필요했습니다. 예를들어서 interval 첫자리 숫자에 대해서 정렬을 하지 않으면 앞뒤로 순회를 해야하는 경우를 고려해야하는데 로직의 복잡도를 줄이기 위해서 정렬을 고려하는 것도 생각해볼 포인트라고 판단됩니다. 나름 재미있게 푼 문제였습니다.