[LeetCode] 56. Merge Intervals (Java)

문제

 

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

Merge Intervals - LeetCode

 

풀이

 

난이도: Medium 

 

이전 문제 [LeetCode] 57. Insert Interval (Java)와 거의 비슷하게 해결할 수 있지만, 추가적인 아이디어도 소개하겠다.

 

일단, 가장 간단한 풀이는 주어진 2차원 배열을 정렬 후에 겹치는(overlapping) 부분을 합치면 된다.

자바에서의 2차원 배열의 정렬은 Comparator 인터페이스의 compare 메서드를 구현하여 사용한다.

(인터페이스를 활용해서 그런지, C++의 STL처럼 2차원 배열 정렬을 기본으로 지원하진 않는 듯하다.)

특히 comparing 메서드를 이용하면 메서드 참조나 람다식을 비교 함수로써 넘겨주어 빠르게 정렬을 구현할 수 있다.

 

이번 문제는 start가 같을 때 end의 차이로 순서가 달라질 필요가 없으므로 첫 번째 값만을 기준으로 오름차순 정렬을 하자.

장렬이 끝났다면 다음 구간의 시작점이 이번 구간의 end보다 작거나 같다면 두 구간은 합칠 수 있다.

만약 다음 시작점이 end보다 크다면 두 구간은 합쳐질 수 없으므로 이번 구간은 현재의 start, end지점으로 구간이 확정된다.

 

코드

 

문제의 Discuss장에 올라온 더 효율적인 풀이도 소개하겠다.

풀이의 핵심은 구간으로 짝지어진 시작점(start)과 끝(end)을 때어내어 독립적으로 생각하는 것이다.

start와 end를 다른 배열에 저장하고 각 배열을 정렬한다.

 

start와 end를 순서대로 비교할 때, 구간이 분리되는 경우는 이번(idx) end가 다음(idx+1)의 start보다 작은 경우이다.

다음 시작이 이번의 끝보다 작다면 여전히 구간은 겹치고 분리될 때까지 idx를 증가시키며 확인하면 된다.

 

구간이 겹치는 경우 [3,6]과 [4,5]는 첫 번째 구간이 두 번째 구간보다 end가 크다.

이때 시작과 끝점을 독립적으로 저장해 정렬시키면 다른 결과가 나올 거라 생각할 수 있지만

[3,5]와 [4,6]의 구간도 결국 [3,6]의 구간으로 합쳐진다.

결국 시작점과 끝점을 때어놓고 생각해도 상관이 없다.

 

 

자세한 코드는 아래를 참고하자.

Beat 98% Java. Sort start & end respectively.