Merge Intervals

🔗 문제 링크

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

❔ 문제 설명

Given an array of intervals where intervals $[i] = [start_i, end_i]$, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

⚠️ 제한사항

• $1 <= intervals.length <= 10^4$

• $intervals[i].length == 2$

• $0 <= start_i <= end_i <= 10^4$
  
  

  ---

💡 풀이 (언어 : Java)

깔끔하게 합치는 과정이 떠오르지 않았는데, 시작 지점, 끝나는 지점을 변수로 따로 선언하고 두 범위가 겹치면 end 값을 더 큰값으로 갱신하고 겹치지 않는 범위가 나왔을 때 새로 배열을 만들어서 거기에 담아서 List에 넣어주면 됐다. 정답은 배열로 반환해야 하는데 정답 배열안의 원소가 몇개가 나올지는 알 수 없기 때문에 List에 넣어주고 마지막에 배열로 변환해서 반환했다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> answer = new ArrayList<>();
        // start 기준으로 오름차순 정렬
        Arrays.sort(intervals, (a, b) -> a[0]-b[0]);
        // 첫 원소로 기준 만들기
        int start = intervals[0][0], end = intervals[0][1];
        // 두번째 원소부터 조회 시작
        for (int i = 1; i < intervals.length; i++) {
            // 앞의 start가 뒤의 end 이하인 경우, start는 그대로 end는 둘중에 더 긴쪽 채택
            if (intervals[i][0] <= end)
                end = Math.max(end, intervals[i][1]);
            // 앞의 start가 뒤의 end가 겹치지 않는 경우, 정답 리스트에 넣어주고 start, end 현재 원소로 갱신
            else {
                answer.add(new int[] {start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        // 마지막 원소는 반복문에서 들어가지 않으므로 여기서 넣기
        answer.add(new int[] {start, end});
        return answer.toArray(new int[answer.size()][]);
    }
}