Sorting 기반 Single Pass 스캔으로 시간 복잡도 O(N log N) 달성

Context

Interval 기반 데이터 처리 시 중복 구간 식별을 위해 모든 조합을 비교하는 Brute Force 방식의 한계 발생. 무작위 배치 상태의 데이터 구조로 인해 O(N²)의 높은 시간 복잡도 및 불필요한 반복 연산 수행.

Technical Solution

• Start Time 기준 정렬을 통한 인접 구간 간의 Overlap 가능성 확보
• 정렬 후 데이터의 선형적 배치를 통한 Single Pass 스캔 구조 설계
• 가장 최근에 병합된 구간의 End Time과 현재 구간의 Start Time을 비교하는 단일 조건문 적용
• Overlap 확인 시 End Time을 기존 값과 현재 값의 Max 값으로 갱신하여 구간 확장 수행
• 비중첩 구간 발견 시 즉시 결과 리스트에 추가하여 메모리 효율 최적화

Impact

• 시간 복잡도: O(N²)에서 O(N log N)으로 성능 개선
• 공간 복잡도: O(N) 유지하며 처리 효율성 극대화

Key Takeaway

데이터 간의 상대적 위치 관계가 중요한 문제에서 정렬(Sorting)을 통한 데이터 정규화가 전체 알고리즘의 복잡도를 획기적으로 낮추는 핵심 전략임.