[leetcode #56] Merge Intervals

Problem

Given an array of intervals where intervals[i] = [startᵢ, endᵢ], 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⁴
・ intervals[i].length == 2
・ 0 <= startᵢ <= endᵢ <= 10⁴

Idea

주어진 interval을 overlap한 결과를 구하는 문제다.

우선 주어진 interval을 첫 번째 시작점을 기준으로 정렬한다. (O(NlogN))

첫 번째 interval은 결과에 그대로 넣은 뒤, 나머지 interval을 탐색한다. 현재 interval과 결과에 있는 interval을 차례로 비교한다. 현재 interval의 시작점이 결과의 interval 사이에 있을 경우 결과 interval의 끝지점을 두 interval의 끝지점 중 큰 값으로 정한다. 만약 현재 interval이 결과에 있는 interval과 overlap되는 영역이 없다면 새로운 interval로 결과에 그대로 더한다. 그리고 다음에 탐색할 결과 interval의 index도 1 올려준다.

이 과정을 반복하면 overlap한 결과가 얻어진다.

Solution

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (int[] a, int[] b) -> a[0] - b[0]);

        List<int[]> list = new ArrayList<>();
        list.add(new int[]{intervals[0][0], intervals[0][1]});

        int index = 0;
        for (int i=1; i < intervals.length; i++) {
            int[] current = intervals[i];
            int[] resCurrent = list.get(index);

            if (current[0] >= resCurrent[0] && current[0] <= resCurrent[1]) {
                resCurrent[1] = Math.max(resCurrent[1], current[1]);
            } else {
                list.add(new int[]{current[0], current[1]});
                index++;
            }
        }

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

훌륭한 결과가 나왔다. 😆

Reference

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