[LeetCode] 56. Merge Intervals

Problem

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] overlap, 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 <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

---

Solution

class Solution {
    public int[][] merge(int[][] intervals) {
        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];
        
        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        
        Arrays.sort(start);
        Arrays.sort(end);
        
        int startIndex = 0;
        int endIndex = 0;
        List<int[]> list = new ArrayList<int[]>();
        
        while (endIndex < intervals.length) {
            if (endIndex == intervals.length - 1 || end[endIndex] < start[endIndex + 1]){
                list.add(new int[]{start[startIndex], end[endIndex]});
                startIndex = endIndex + 1;
            } endIndex++;
        } return list.toArray(new int[list.size()][]);
    }
}

Explanation

• 배열 intervals에서 인접한 두 배열이 겹치는지를 알기 위해선 앞 배열의 뒷 요소와 뒷 배열의 앞 요소를 비교해야 한다. 뒷 배열의 앞 요소가 앞 배열의 뒷 요소보다 작다면 두 배열은 겹쳐지는 부분이 있는 것이고, 하나의 배열로 합쳐져야 한다.
• 앞 배열의 뒷 요소와 뒷 배열의 앞 요소를 쉽게 비교하기 위해서 각 요소를 배열을 선언하고, for 반복문을 사용하여 각 요소를 담는다.

int[] start = new int[intervals.length];
int[] end = new int[intervals.length];

for (int i = 0; i < intervals.length; i++) {
    start[i] = intervals[i][0];
    end[i] = intervals[i][1];
}

• 이 때, 배열 start와 배열 end가 정렬되어 있지 않다면 잘못된 interval을 생성할 수 있는 경우의 수가 생기므로 두 배열을 정렬해준다.

  Arrays.sort(start);
  Arrays.sort(end);
  

• 반복을 통해 배열 start와 배열 end속 요소를 비교하고, 새로운 interval을 만들기 위해 각 배열 속 요소를 참조하는 변수 startIndex와 변수 endIndex를 선언한다.
• 결과 반환은 2차원 배열로 해야하지만, 배열은 크기를 조정할 수 없으므로, 결과 반환을 위한 리스트를 선언한다.

  int startIndex = 0;
  int endIndex = 0;
  List<int[]> list = new ArrayList<int[]>();
  

• while 반복문을 선언해서 배열 start와 배열 end의 값을 비교한 후 새로운 interval을 만들고, 리스트에 추가하도록 한다.

  while (endIndex < intervals.length) {
    if (endIndex == intervals.length - 1 || end[endIndex] < start[endIndex + 1]){
        list.add(new int[]{start[startIndex], end[endIndex]});
        startIndex = endIndex + 1;
    } endIndex++;
  }
  

• 리스트를 2차원 배열로 변경하여 반환하도록 한다.

  return list.toArray(new int[list.size()][]);