LeetCode - Merge Intervals

문제 설명

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.

Constrains

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

Solution

• 처음에 주석 처리한 방식으로 for문을 하나 더 써서 풀었더니, input으로 [1,2][3,4][5,6],[7,8][1,10] 들어오는 예제에 오류가 났다.
• 순서대로 input이 들어오면 이런일이 없을텐데 하는 생각이 들어서 sorting을 먼저했다. sorting을 하고보니 이미 담긴 arraylist도 마지막꺼와만 비교하면 된다.
• 처음 방법이 best는 아니었지만, 개선하는 방향성에 힌트를 줬다. best부터 한참 고민하기 보다는, 생각나는 아이디어로 풀어보고 best인지 체크후 개선하는 방향이 역시 좋다.

class Solution {
    public int[][] merge(int[][] intervals) {
        

        //intervals를 sorting 하자 : 처음에 정렬을 해줘야 나중에 앞의 범위를 포괄하는 큰 케이스를 다루는 경우가 없음
        /*
        ex. [1,2][3,4][5,6],[7,8][1,10]
        */
        // Arrays.sort(intervals, new Comparator<int[]>(){
            
        //     @Override
        //     public int compare(int[] preArr, int[] nextArr){
        //         return preArr[0] - nextArr[0];
        //     }
        // });
        Arrays.sort(intervals, (a,b)->Integer.compare(a[0],b[0]));

        ArrayList<int[]> mergeArray= new ArrayList<int[]>();

        
        mergeArray.add(intervals[0]);

        for(int i=1; i<intervals.length; i++){
       
            // 순서대로 정렬되어있기 때문에 마지막꺼랑만 비교하면됨
            int idx=mergeArray.size()-1;
            int[] mergeItem=mergeArray.get(idx);
            if(intervals[i][0]<=mergeItem[1] ){
                if(intervals[i][1]>mergeItem[1]){
                            mergeArray.get(idx)[1]=intervals[i][1];
                }   //같거나 작으면 수정할 필요 없음.
            }else{
                 mergeArray.add(intervals[i]);
            }
            
                // sorting을 먼저함으로써 필요없어진 아래 로직들
                //  int j=0;
                // int merLen=mergeArray.size();
                //for(; j<merLen; j++){ // 이미 들어가있는 arraylist를 참조함
                // 시작점보다 같거나 킅경우
                // if(mergeItem[0]==intervals[i][0] || (mergeItem[0]<intervals[i][0] && intervals[i][0]<=mergeItem[1]) ){
                //     if(intervals[i][1]>mergeItem[1]){
                //             mergeArray.get(j)[1]=intervals[i][1];
                //     }   //같거나 작으면 수정할 필요 없음.
                //     break;
                // }else if(mergeItem[0]<intervals[i][0] && intervals[i][0]<=mergeItem[1]){ // 
                //      if(intervals[i][1]>mergeItem[1]){
                //             mergeArray.get(j)[1]=intervals[i][1];
                //     }   //같거나 작으면 수정할 필요 없음.
                //     break;
                // }
                // else if(mergeItem[0]>intervals[i][0] && intervals[i][1]>=mergeItem[0]){ // 시작점보다 작은경우  
                //     mergeArray.get(j)[0]=intervals[i][0];
                //     if(intervals[i][1]>mergeItem[1]){
                //             mergeArray.get(j)[1]=intervals[i][1];
                //     }   //같거나 작으면 수정할 필요 없음.
                //     break;
                // }     
                //  }
                //     if(j>=merLen) // 겹치는 부분이 없었음
                //     {
                //         mergeArray.add(intervals[i]);
                //     }
        }
        // int[][] mergeArr=new int[mergeArray.size()][2];
        // for(int k=0; k<mergeArr.length; k++){
        //     mergeArr[k][0]=mergeArray.get(k)[0];
        //     mergeArr[k][1]=mergeArray.get(k)[1];
        // }

        int[][] mergeArr=mergeArray.stream()
                                    .map(l -> l)
                                    .toArray(int[][]::new);
        
        return mergeArr;
    }
}