[LeetCode] 56. Merge Intervals

문제 설명

문제 풀이

• 정렬을 이용한 아이디어가 필요했다.
• intervals를 start를 기준으로 정렬한 후, for문을 통해 각 원소를 순회하는데 S, E를 두어 아래와 같은 룰을 적용하면 답을 구할 수 있다.

  1) 현재 start가 E보다 작은경우 (머지하는 경우) E = max(현재 end, E)로 지정.
  2) 현재 start가 E보다 큰 경우 (머지 안해도 되는 경우) (S, E)를 결과에 추가해줌, S / E 다시 지정.

소스 코드 (JAVA)

class Solution {

    public int[][] merge(int[][] intervals) {
        // sort our intervals 
        Arrays.sort(intervals, (o1,o2)->o1[0]-o2[0]);

        ArrayList<int[]> ans  =  new ArrayList<>();
        int start  =  intervals[0][0];
        int end =  intervals[0][1]; 

        int  i =1;
        while(i<intervals.length){
            int s = intervals[i][0];
            int e = intervals[i][1];
            if( s<=end  ) { 
                       // so merge both intervals 
                end =  Math.max(end,e);
            }
            else{ // if merge not possible , then insert prev interval into list
                ans.add(new int[]{start,end});
                start = s;
                end =  e;                
            }
            i++;
        }

        ans.add(new int[] {start,end});

        return ans.toArray(new int[0][]);
    }
}