[LeetCode] 56번 - Merge Intervals [Swift]

문제 링크

Merge Intervals - LeetCode

문제 

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] overlaps, 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,3] 의 경우 1이 중요한거죠!

그래서 작은 수를 기준으로 오름차순 정렬을 시켜준뒤 배열의 처음부터 병합여부를 보고 병합이 된다면 병합을 하고 병합을 할 수 없다면 결과에 현재 값을 추가해줬습니다.

병합여부를 판단하는 방법은, 일단 작은 수를 기준으로 오름차순을 했기 때문에 배열 인덱스가 작은 범위를 a 라고 하고 배열 인덱스가 큰 범위를 b라고 했을 때 a의 최대값이 b의 최소값보다는 커야지 병합이 가능했습니다.

 

예를 들어 [1,3],[2,6]의 경우 [1,3]의 최대값인 3이 [2,6]의 최소값인 2보다 크기 때문에 병합이 가능한거에요.

사실 말로해서 헷갈릴 수 있는데 그림만 보면 위와 같이 겹쳐진다는 말로 이해할 수 있어요.

 

어쨌든 저렇게 겹쳐지면 [1,6]으로 병합한 뒤 다음 값을 확인합니다.

[1,6], [8,10]에서 6이 8보다 작기 때문에 병합을 할 수 없습니다.

오름차순으로 정렬을 해놨기 때문에 이 말은 더이상 병합할 수 있는 값이 존재하지 않는다는 것이므로 [1,6]을 정답에 넣어주시면 됩니다.

이를 반복하시면 답을 구할 수 있었습니다!

소스 코드

class Solution {
    func merge(_ intervals: [[Int]]) -> [[Int]] {
        let sortIntervals = intervals.sorted { (a, b) -> Bool in
            return a[0] < b[0]
        }
        var result: [[Int]] = []
        var now: [Int] = sortIntervals[0]
        
        for i in 1..<sortIntervals.count {
            if now[1] >= sortIntervals[i][0] {
                now = [now[0], max(now[1], sortIntervals[i][1])]
            } else {
                result.append(now)
                now = sortIntervals[i]
            }
        }
        result.append(now)
        
        return result
    }
}