시작점으로 구간 정렬하기

구간은 시작점과 끝점처럼 두 숫자의 쌍일 뿐이며, 예를 들면 [2, 5]와 같습니다. 대부분의 구간 문제는 이러한 쌍의 목록으로 주어집니다. 📏

정렬되지 않은 구간은 어떤 순서로든 주어질 수 있어 이해하기 어렵습니다. 먼저 정렬하면 뒤섞인 목록이 깔끔한 왼쪽에서 오른쪽 방향의 탐색으로 바뀝니다.

기본적으로 시작 값으로 정렬합니다. 그러면 각 구간이 앞 구간과 같거나 그보다 뒤에서 시작하므로 한 번 앞으로 훑을 수 있습니다.

구간을 튜플로 저장하면 Python은 별도 작업 없이 첫 번째 요소를 기준으로 정렬하고, 그다음 두 번째 요소를 기준으로 정렬합니다. 여기에는 키 함수도 필요하지 않습니다.

시작점을 기준으로 정렬하면 사건을 시간 순서대로 처리할 수 있습니다. 다음 구간은 현재 구간보다 늦게 시작할 수밖에 없으며, 이것이 훑기에서 중요한 불변식입니다.

두 구간의 시작점이 같다면 두 번째 기준이 순서를 결정합니다. (시작점, 끝점)으로 정렬하면 짧은 구간이 먼저 오므로 유용한 경우가 많습니다.

가장 많은 사건을 일정에 배치하는 문제처럼 일부 문제에서는 끝점으로 정렬합니다. 훑기에서 알아야 할 정보에 맞는 기준을 선택하십시오.

정렬에는 O(n log n) 시간이 걸리며, 이는 저렴한 편이고 보통 이러한 문제의 지배적인 비용입니다. 그다음에 수행하는 훑기는 O(n)에 불과합니다.

각 구간에 식별자나 가중치가 포함되어 있다면 경계만이 아니라 전체 데이터를 정렬하십시오. 기준이 순서를 결정하고 데이터는 함께 이동합니다.

거의 모든 구간 알고리즘은 sort 먼저, 그다음 훑기 방식입니다. 순서를 올바르게 정하면 병합, 개수 세기, 일정 배치가 간단한 반복문이 됩니다.

구간을 파티에 도착하는 손님이라고 생각해 보십시오. 시작점으로 정렬하면 손님이 도착하는 순서대로 줄을 세울 수 있어 한 명씩 맞이하면 됩니다.

구간 목록을 병합하려고 합니다.

구간은 시작점과 끝점의 쌍이며, 시작점으로 정렬하면 복잡한 목록이 깔끔한 훑기로 바뀝니다. 먼저 정렬한 다음 O(n)에 앞에서부터 처리하십시오. 🚀