LeetCode 명상: 겹치지 않는 간격

겹치지 않는 간격에 대한 설명은 다음과 같습니다.

간격[i] = [start_i, end_i]인 간격의 배열이 주어지면 나머지 간격을 겹치지 않게 만들기 위해 제거해야 하는 최소 간격 수를 반환합니다.

참고 한 지점에만 닿는 간격은 겹치지 않습니다. 예를 들어 [1, 2]와 [2, 3]은 겹치지 않습니다.

예:

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

또는:

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

또는:

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

---

이 문제에 대해 NeetCode는 이전 문제에서 그랬던 것처럼 간격 정렬부터 시작하는 훌륭한 솔루션을 제공합니다.
제거 횟수를 추적하기 위해 변수를 초기화할 수도 있습니다.

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

let numRemovals = 0;

이제 간격이 정렬되었으므로 각 간격을 살펴보며 겹치는지 여부를 확인하겠습니다. 이를 위해 이전 간격의 end를 추적하므로 처음에 첫 번째 간격의 끝을 보유하는 prevEnd 변수를 초기화하겠습니다.

let prevEnd = intervals[0][1];

참고 두 간격이 겹치지

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.

않는 경우 한 간격의 시작은 간격의 끝보다 엄격히 커야합니다. other 또는 하나의 끝은 엄격하게 장 소개에서 언급한 것처럼 다른 것의 시작보다 작습니다.

이 문제에서는 간격의 끝이 다른 간격의 시작과 같을 때 서로 겹치지 않는 것으로 간주됩니다.

여기서 한 간격의 시작이 다른 간격의 끝보다 엄격하게 작으면 두 간격이 겹친다고 말할 수 있습니다. 이 경우 prevEnd를 두 끝 중 더 작은 값으로 업데이트하여 다음 간격과 겹칠 가능성을 줄입니다. 그렇지 않으면 이전과 같이 계속 진행합니다.

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1

Explanation: [1, 3] can be removed and the rest of the intervals are non-overlapping.

마지막으로 numRemovals를 반환할 수 있습니다.

Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2

Explanation: You need to remove two [1, 2] to make the rest of the intervals non-overlapping.

그리고 우리가 얻은 최종 해결책은 다음과 같습니다.

Input: intervals = [[1, 2], [2, 3]]
Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

시간과 공간의 복잡성

처음부터 간격을 정렬하므로 시간 복잡도는 $오(nlogn)$O(n log n) . 입력 크기가 증가함에 따라 크기가 증가하는 추가 데이터 구조가 없으므로 공간 복잡도는 다음과 같습니다. $O(1)$O(1) .

---

다음으로 시리즈의 마지막 장인 비트 조작(Bit Manipulation)을 시작하겠습니다. 그때까지 즐거운 코딩하세요.

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