[LeetCode] 56. Merge Intervals - 문제풀이

Description

배열이 주어지면 겹치는 모든 간격을 병합 하고 입력의 모든 간격을 포함하는 겹치지 않는 간격의 배열을 반환합니다

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.

Constraints:

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

Solution 1. Sorting

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

    List<int[]> result = new ArrayList<>();
    Arrays.sort(intervals, (o1, o2) -> {
        return o1[0] - o2[0];
    });
    int len = intervals.length;
    if(len == 1) return new int[][]{{intervals[0][0],intervals[0][1]}};

    int start = intervals[0][0];
    int end = intervals[0][1];
    for (int i = 1; i < len; i++) {
        if(start <= intervals[i][0] && intervals[i][0] <= end ){
            end = Math.max(end,intervals[i][1]);
        }else{
            result.add(new int[]{start,end});
            start = intervals[i][0];
            end = intervals[i][1];
        }
    }
    result.add(new int[]{start,end});

    //convert List to Array
    return result.toArray(new int[result.size()][]);
}

Comparator를 이용해 시작 숫자 기준으로 정렬 한 뒤 이전요소와 겹치는 부분이 있는 경우 시작점과 끝점을 합쳐서 기억하고 떨어진 요소를 만났을때 기록해나갑니다. 반복이 끝난 후 마지막 요소를 기록하고 배열로 변환하여 반환하면 됩니다.

Reference

Merge Intervals - LeetCode