[LeetCode] 56. Merge Intervals - 구현(Implementation) JAVA

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

코드설명

구현(Implementation) 을 활용합니다.

 

만약 첫번쨰 Interval의 end 범위가 두번쨰 Interval의 start 범위보다 크다면, 즉, sInterval.end >= nInteraval.start 라면 Merge합니다.

이떄 중요사항은, Math.max로 처리해야 합니다. 이유는 Interval의 nInterval을 포함하는 경우도 Merge 하는 경우라고 판단하기 때문입니다. 

 

혹은 UnionFind로도 풀 수 있습니다만, 아래의 구현이 훨씬 직관적이며 쉽습니다.

 

또한 아래의 코드에서 new Comparator<int[]> 를 직접 구현한점, 그리고 ArrayList를 answer.toArray(new int[answer.size()][])로 편하게 변환한점을 눈여겨보면 좋습니다.

코드

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                return Integer.compare(o1[0], o2[0]);
            }
        });

        ArrayList<int[]> answer = new ArrayList<>();
        int[] sInterval = intervals[0];
        for(int i=1; i<intervals.length; i++){
            if(sInterval[1] >= intervals[i][0]){
                sInterval[1] = Math.max(sInterval[1], intervals[i][1]);
            }
            else {
                answer.add(new int[] {sInterval[0], sInterval[1]});
                sInterval[0] = intervals[i][0];
                sInterval[1] = intervals[i][1];
            }
        }
        answer.add(sInterval);
        return answer.toArray(new int[answer.size()][]);
    }
}