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()][]); } }