(Interval, Medium) Merge Intervals

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

이전 문제와 비슷한데 newInterval과 같은 추가 파라미터를 주는게 아니라 원본 배열 요소 내에서 머지하는 문제다.

핵심은 start 순으로 정렬되어있어야 풀기가 쉽다는 건데, 문제에서 intervals가 정렬된 상태라는 말이 없으므로 배열을 start 기준 오름차순 정렬해주고 진행한다.

정렬 완료 시 첫 번째 원소의 start가 가장 적은 수가 되므로 기준값으로 사용할 수 있다.
그러므로 순회는 0번째가 아니라 1번째부터 하면서 찾아도 된다.

이전 문제와 마찬가지로 가능한 경우는 3가지다 - "머지 가능", "왼쪽", "오른쪽"
기준값의 start와 end, 그리고 현재 원소의 start와 end를 비교해서 이것을 구할 수 있다.

원리는 이전 문제와 동일하므로 어렵지 않게 풀 수 있음
Java는 참조타입 배열 sort시 timsort 사용하므로 최악 시간복잡도도 O(N log N)임

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

        int start = intervals[0][0];
        int end = intervals[0][1];

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

        for (int i=1; i<intervals.length; i++) {
            
            if (intervals[i][0] > end) {
                list.add(new int[] { start, end });
                start = intervals[i][0];
                end = intervals[i][1];

            } else if (intervals[i][1] < start) {
                list.add(new int[] { intervals[i][0], intervals[i][1] });

            } else {
                start = Math.min(start, intervals[i][0]);
                end = Math.max(end, intervals[i][1]);
            }
        }
        list.add(new int[] { start, end });

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