날짜 범위의 컬렉션이 주어진 나머지 연도부터 모든 누락 날짜 범위를 찾아야합니다. 모든 날짜 범위는 같은 해에 속합니다. 그리고 날짜 범위 사이에 겹침이 없습니다.누락 날짜 범위
예 : [(1/31/2011 - 5/1/2011), (6/5/2011 - 12/1/2011)]은 콜렉션에서 사용할 수 있습니다. 누락 날짜 범위는 [(1/2011 년 5 월 2 일 ~ 2011 년 6 월 30 일), (12/2/2011-12/31/2011)]
효율적인 방법은 이 문제를 해결 하시겠습니까?
겹침이없고 모든 범위가 같은 해 인 경우 범위를 시작 시간순으로 오름차순으로 정렬 할 수 있습니다. 그런 다음 누락 된 범위는 1 월 1 일과 첫 번째 시작 날짜 사이, 모든 범위 사이 및 마지막 범위 끝에서 12 월 31 일 사이가됩니다. 발생할 수있는 빈 범위를 필터링해야합니다 (예 : , 다음 범위가 시작 되 자마자 한 범위가 끝나는 경우).
이 알고리즘은 범위를 정렬하는 데 O (nlog n) 시간이 걸리고 누락 된 범위를 찾는 데 O (n) 시간이 걸립니다. 또는 고유 한 정렬 함수를 구현하려는 경우 버킷 정렬이나 기수 정렬을 사용하여 O (n) 시간 범위를 정렬 할 수 있습니다. 가능한 날짜 범위가 작고 유한하므로 정렬합니다. 첫 번째 버전은 구현하기가 더 쉽고 O (n log n) 시간에 실행되고 두 번째 버전은 O (n)에 실행됩니다.
희망이 도움이됩니다.