구간 겹침 코딩테스트: 같은 시각의 시작과 종료를 처리하기

구간 겹침 코딩테스트의 sweep line에서 같은 시각에 시작과 종료가 겹치면, 이벤트 정렬 순서는 구간의 끝점을 포함하는지에 따라 결정됩니다. 반열린 구간 [s,e)에서는 종료를 먼저 처리하지만, 닫힌 구간 [s,e]에서는 시작을 먼저 반영합니다. 두 계약을 예제와 코드로 비교하고 빈 구간, 방 배정, 오라클 검증까지 다룹니다. PracHub의 Merge Overlapping Intervals with a Sweep는 특정 응시 시험을 예측하지 않는 연습 자료입니다.

근거 범위. 공식 언어 문서는 라이브러리 동작의 근거입니다. 아래 불변식과 풀이의 정당성은 명시한 입력 계약에 따른 유도이며, 배열·그래프·시간축과 검산 코드는 이 글의 합성 교육 사례입니다. 후보자 보고나 특정 회사의 출제 형식은 사용하지 않았습니다.

가장 먼저 끝점 계약을 질문하기 (Endpoint contract)

구간 [start,end)는 시작을 포함하고 끝을 제외하는 반열린 구간입니다. 이 계약에서는 [1,4)와 [4,6)이 겹치지 않습니다. 두 번째 구간은 시각 4부터 유효하지만 첫 번째는 시각 4 직전에 끝났기 때문입니다. 반대로 양 끝을 모두 포함하는 [1,4], [4,6] 모델에서는 시각 4를 함께 포함해 겹칩니다.

따라서 “동일 시각의 이벤트를 어떤 순서로 정렬할까요?”라는 질문은 먼저 구간 의미를 확인해야 답할 수 있습니다. 반열린 계약이라면 같은 시각에 종료를 먼저 처리하고, 닫힌 구간 계약이라면 시작을 먼저 처리합니다. 시간 슬롯을 세는 구현에서는 이벤트에 (time, delta)를 저장하고 delta 오름차순 정렬로 종료 -1을 시작 +1보다 앞에 둘 수 있습니다.

최대 동시 구간 수를 세는 sweep (Sweep events)

반열린 구간의 최대 동시 개수를 세는 간단한 코드는 다음과 같습니다. 시작과 종료를 한 시각에 묶어 순서대로 적용하면 끝점 규칙이 눈에 보입니다. start == end인 빈 구간은 활동 구간 수에 영향을 주지 않으므로 제외합니다. 입력 시간의 정밀도나 시간대 변환은 문제 계약에 맞춰 별도로 정해야 합니다.

def max_overlaps(intervals):
    events = []
    for start, end in intervals:
        if start > end:
            raise ValueError("start must not exceed end")
        if start == end:  # [t,t)는 빈 구간
            continue
        events.append((start, +1))
        events.append((end, -1))
    active = best = 0
    for time, delta in sorted(events, key=lambda e: (e[0], e[1])):
        active += delta  # 같은 시간에는 -1 종료가 +1 시작보다 먼저
        best = max(best, active)
    return best

구간이 [2,5), [5,8)이면 시각 5에서 활성 수가 1에서 0으로 내려간 후 다시 1이 됩니다. 두 개가 동시에 활성인 순간은 없습니다. [2,7), [5,8)이라면 시각 5의 시작 때 첫 구간도 아직 살아 있어 최대는 2입니다.

병합과 방 배정은 같은 문제인가? (Concurrency vs coverage)

겹치는 구간을 합쳐 덮인 범위를 구하는 문제와, 동시에 필요한 방 수를 구하는 문제는 입력은 같아도 답의 의미가 다릅니다. 병합은 인접 구간을 합칠지까지 계약해야 합니다. 반열린 구간 [1,4)와 [4,6)은 겹치지 않지만, “끊김 없는 커버리지 덩어리”로 인접 구간을 합칠 수는 있습니다. 방 배정에서는 경계가 맞닿는 회의를 같은 방에서 연이어 할 수 있으므로 종료 시각이 시작보다 작거나 같을 때 방을 재사용합니다.

모든 이벤트를 정렬하면 O(n log n) 시간, O(n) 공간입니다. 회의가 이미 시작 순으로 주어지고 실제 배정도 필요하다면 종료 시각 최소 힙을 활용할 수 있습니다. 최대 동시 개수만 필요하면 정렬된 이벤트 누적합이면 충분합니다.

최대 동시 구간 수, 합집합 길이, 회의실 배정은 같은 정렬 이벤트를 사용해도 집계 기준이 다릅니다. [1,3)과 [3,5)의 합집합 길이는 4이고 끊김 없는 한 덩어리로 합칠 수 있지만, 동시에 사용하는 방은 1개입니다. 최대 겹침 수는 활성 개수의 최댓값입니다. 반환할 답이 길이인지, 병합된 구간인지, 동시 사용량인지 먼저 고르면 필요한 상태와 접점 처리 방식이 분명해집니다.

회의실 번호까지 배정한다면 가장 빨리 끝나는 회의를 추적하는 최소 힙을 쓸 수 있습니다. 반열린 구간에서는 가장 이른 종료 시각이 현재 회의 시작과 같아도 그 방을 재사용할 수 있습니다. 방 수만 필요할 때는 종료 시각이 같은 방 중 어느 것을 골라도 답이 같지만, 방 번호를 반환한다면 동률일 때 선택할 방을 결정해야 결과가 재현 가능합니다. 테스트에는 같은 시작, 같은 종료, 세 회의의 동시 접점을 넣어 순서와 방 수를 각각 검증하세요.

경계값을 작은 시간 격자와 대조하기 (Oracle tests)

정수 시각을 사용하는 테스트에서는 각 단위 구간 [t,t+1)에서 활성 구간을 직접 세는 오라클을 만들 수 있습니다. 테스트 집합에 동일 구간 중복, 같은 시작, 중첩, 접점, 빈 구간을 넣고 sweep 결과와 비교하세요. 닫힌 구간이라면 정수 점을 직접 세는 오라클로 바꿔야 합니다. 반열린 계약의 테스트를 닫힌 구간 정답과 비교하면 정렬 코드가 옳아도 테스트가 틀립니다.

연습 자료에서 끝점 가정을 확인하기 (Practice)

종료 이벤트가 먼저인 이유를 시간축으로 설명하기 (Tie ordering)

반열린 구간 [s,e)는 시작 s를 포함하고 e를 포함하지 않습니다. 시각 t에서 구간이 활성이라는 조건은 s <= t < e입니다. 따라서 종료가 t인 구간은 시각 t에 이미 비활성이고, 시작이 t인 구간은 그 시각부터 활성입니다. 같은 시각의 겹침을 계산하려면 먼저 종료를 반영하고 시작을 더하면 됩니다. 이 정의가 event sort의 delta 우선순위를 정합니다.

닫힌 구간 [s,e]는 s <= t <= e를 만족합니다. 끝점 t에 도착하기 전 종료 구간을 제거하면 해당 점에서 두 구간이 만난다는 사실을 잃습니다. 그러므로 시작을 먼저 반영합니다. 두 가지 구현을 모두 요구할 수 있는 문제라면 구간 표현을 매개변수로 받아 우선순위와 비교 연산을 함께 바꾸어야 합니다. 정렬키만 바꾸고 오버랩 테스트 조건을 그대로 두면 서로 다른 의미가 혼합됩니다.

빈 구간과 잘못된 입력을 분리하기 (Empty intervals)

[t,t)는 어떤 시각에도 활성이지 않으므로 앞 코드처럼 무시할 수 있습니다. [t,t]는 닫힌 구간 계약이라면 점 t 하나를 포함합니다. 이 차이는 스윕 결과에서만 끝나지 않습니다. 빈 구간을 병합할지, 회의 한 건으로 볼지, 입력 오류로 거부할지에 따라 반환된 구간 집합이나 방의 수가 달라집니다. start>end는 일반적으로 잘못된 입력이므로 검증 오류로 처리하되, 문제 설명이 별도 정규화를 요구하면 그 규칙을 따릅니다.

시각이 정수라면 실제 업무의 “분” 또는 “초”가 연속인지 이산인지도 확인해야 합니다. 한 구간이 09:00부터 10:00까지이고 다음이 10:00부터 11:00까지인 회의는 끝과 시작의 동시 점이 실제 사용 충돌인지 조직의 예약 정책이 결정합니다. 알고리즘은 전달받은 계약을 계산할 뿐, 회의실 정책을 대신 정하지 않습니다.

다음 연습에서 설명할 한 가지 (Next exercise)

오늘은 Compute the Minimum Number of Meeting Rooms를 풀면서 경계 이벤트의 순서를 정한 다음 경계 사례 하나와 시간·공간 복잡도를 소리 내어 설명해 보세요. Practice 자료는 연습을 위한 기록이며 실제 시험 문제를 예측하지 않습니다.

같은 시각 이벤트를 한 묶음으로 처리하기 (Grouped timestamps)

이벤트를 (시각, 변화량)으로 펼치고 반열린 구간에 맞춰 종료 -1을 시작 +1보다 먼저 정렬할 수 있습니다. 다만 최대값만 필요할 때는 같은 시각의 모든 변화량을 묶어 적용하는 방법도 있습니다. 시각 바로 전의 활성 개수에서 종료를 빼고, 그 시각부터 시작하는 구간을 더한 후, [t,next_t)에서의 활성 개수를 기록하면 됩니다. 핵심은 동시성의 정의가 같은 순간의 점 개수인지, 양의 길이를 가진 겹침인지 분리하는 것입니다.

닫힌 구간에서는 같은 시각에 시작하는 구간도 해당 시각에서 활성이고, 끝나는 구간도 그 점에서 활성입니다. 따라서 이벤트 순서를 정할 때 증가를 먼저 반영해야 합니다. 시간 단위가 날짜라면 종료일을 다음 날로 바꾸어 반열린 구간으로 정규화하는 방식이 자주 쓰이지만, 원본 시스템의 날짜·시간대·초 단위 계약이 우선입니다. 정규화는 입력 의미를 알고 있을 때만 적용할 수 있습니다.

스윕 라인과 힙 중 어떤 설명을 택할까? (Room assignment)

최대 동시 사용량만 묻는다면 이벤트를 정렬하고 누적 합을 구하는 것이 직접적입니다. 각 회의의 방 번호까지 배정해야 한다면 활성 회의의 종료 시각을 최소 힙에 넣어 가장 빨리 비는 방을 재사용할 수 있습니다. 이 경우 종료가 현재 시작과 같은 방을 재사용해도 되는지 역시 [start,end) 계약에 달려 있습니다.

테스트를 설계할 때는 입력 순서가 같아도 처리 결과가 달라지지 않는지, 같은 시각의 이벤트 정렬이 결정적인지 확인합니다. 동률 이벤트의 상대순서에 의존하지 않도록 그룹 처리하는 방법도 있고, 이벤트 tuple에 정렬 우선순위를 명시하는 방법도 있습니다.

Sources and Further Reading

• Python Sorting Techniques — 이벤트를 결정적으로 정렬하는 공식 Python 문서. 끝점 계약은 본문 합성 예제에서 선언합니다.
• Python heapq — 회의실 배정에서 가장 빨리 끝나는 활성 회의를 찾는 우선순위 큐 문서.
• C++ working draft: Sorting and related operations — 사용자 비교가 strict weak ordering을 이루어야 하는 C++ 정렬 계약.