LeetCode 명상: 병합 간격

병합 간격에 대한 설명부터 시작하겠습니다.

간격[i] = [start_i, end_i]인 간격 배열이 주어지면 겹치는 모든 간격을 병합하고 입력의 모든 간격을 포괄하는 겹치지 않는 간격의 배열을 반환합니다.

예:

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].

또는:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 

---

나중에 쉽게 비교할 수 있도록 먼저 간격을 정렬하는 것부터 시작할 수 있습니다.

intervals.sort((a, b) => a[0] - b[0]);

또한 처음에 새로 정렬된 간격의 첫 번째 요소를 보유하는 결과 배열을 초기화할 수 있습니다.

let result = [intervals[0]];

마지막으로 병합된 간격의 끝을 추적하여 현재 간격의 시작과 비교하여 겹치는지 확인해야 합니다.

참고 두 간격이 겹치지 않도록, 한 간격의

Note

For two intervals not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

시작이 끝보다 엄격히 커야합니다. 다른 하나 또는 한 쪽의 끝은 다른 쪽보다 엄격히 작아야합니다. 장 소개에서 언급한 다른 시작.

겹치지 않으면 해당 간격을 결과에 추가하면 됩니다. 그렇지 않으면 "마지막 끝"을 업데이트하여 간격을 효과적으로 병합해야 합니다.

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].

그리고 남은 일은 결과를 반환하는 것뿐입니다.

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 

그리고 TypeScript에서의 최종 솔루션은 다음과 같습니다.

intervals.sort((a, b) => a[0] - b[0]);

시간과 공간의 복잡성

간격을 정렬하고 있으며 내장된 정렬 기능에는 $오(nlogn)$O(n log n) 시간 복잡도. (루핑은 $O(n)$O(n) , 그러나 전체적인 시간 복잡도는 $오(nlogn)$O(n log n) ).

입력 배열 간격의 크기가 커짐에 따라 결과 배열의 크기도 커질 수 있으므로 다음과 같습니다. $O(n)$O(n) 공간 복잡도.

---

다음으로 비중복 간격 장의 마지막 문제를 살펴보겠습니다. 그때까지 즐거운 코딩하세요.

위 내용은 LeetCode 명상: 병합 간격의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!