Merge Intervals

구간은 시작과 끝이 있는 정수의 범위입니다. 하나 이상의 점을 공유하는 구간은 하나로 합치며, 서로 맞닿기만 하는 구간도 마찬가지입니다. [1, 4]와 [4, 5]는 [1, 5]가 됩니다. 목표는 서로 겹치는 모든 구간 그룹을 그 그룹 전체를 포함하는 하나의 구간으로 바꾸는 것입니다.

핵심은 순서입니다. 구간을 시작점 기준으로 정렬하면, 만들고 있는 구간과 겹치는 구간은 바로 뒤에 옵니다. 정렬된 목록을 차례로 살펴보며 마지막으로 병합한 구간을 유지합니다. 다음 구간의 시작점이 현재 구간의 끝점 이하이면 끝점을 늘리고, 그렇지 않으면 실제 간격이 있으므로 새 구간을 시작합니다. 정렬에는 O(n log n)이 걸리고, 목록을 살펴보는 과정은 한 번만 수행됩니다.

mergeIntervals라는 이름의 함수를 작성하세요. 이 함수는 두 정수 배열 starts와 ends를 입력받아 병합된 구간을 반환합니다.

여기서는 모든 언어가 2차원 배열을 입력으로 받는 것을 지원하지 않으므로 구간은 두 배열로 주어집니다. 구간 i는 [starts[i], ends[i]]이며, 두 배열의 길이는 같습니다. 구간은 정렬되어 있지 않습니다.

겹치는 모든 구간을 병합하세요. 끝점에서만 맞닿는 구간도 겹치는 것으로 간주합니다. 병합된 구간을 시작점 기준으로 정렬된 2차원 배열 [[start, end], ...]로 반환하세요.

예를 들어, starts = [5, 1, 12, 3]과 ends = [7, 4, 14, 6]은 [5, 7], [1, 4], [12, 14], [3, 6]을 나타내며, 이 구간들은 병합되어 [[1, 7], [12, 14]]가 됩니다.

제약 조건: 1 <= starts.length == ends.length <= 10^4, 0 <= starts[i] <= ends[i] <= 10^4.