Leet code (Medium) : 56. Merge Intervals - JAVA

 

 

간격의 배열이 주어지면, 중복된 부분은 합치면서 최적화된 배열을 리턴하는 문제이다.

합치는 과정을 잘하려면 초기에 간격의 시작점을 기준으로 오름차순 정렬을 하고 합치기를 시작해야한다.

 

 

class Solution {
    public int[][] merge(int[][] intervals) {
        
        int n = intervals.length;

        List<int[]> output = new ArrayList<>();

        // start를 기준으로 오름차순 정렬,
        // start가 같을 땐, end를 기준으로 오름차순 정렬
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return Integer.compare(a[1], b[1]);
            } else {
                return Integer.compare(a[0], b[0]);
            }
        });

        output.add(intervals[0]);

        int i = 1; 
        while(i < n){
            int prevStart = output.get(output.size()-1)[0];
            int prevEnd = output.get(output.size()-1)[1];

            int nowStart = intervals[i][0];
            int nowEnd = intervals[i][1];

            if(prevEnd >= nowStart){
                output.get(output.size()-1)[1] = Math.max(prevEnd, nowEnd);
            } else {
                output.add(intervals[i]);
            }

            i++;
        }

        return output.toArray(new int[0][]);    
        // new int[0][] 대신 new int[output.size()][] 도 가능
    }
}