Ch.11 고급 자료구조

Interval 문제 — 겹치는 구간 다루기

Merge Intervals 패턴을 이해하고 구현한다Meeting Rooms 문제에서 최소 회의실 수를 구한다정렬 + 스캔 전략으로 Interval 문제를 체계적으로 접근한다

회의실이 몇 개나 있어야 할까?

10개의 회의가 잡혀 있습니다. 어떤 회의는 겹치고, 어떤 건 안 겹칩니다. 동시에 최대 몇 개의 회의가 진행되는지 알아야 회의실 수를 정할 수 있습니다.

모든 쌍을 비교하면 O(n²). 더 빠른 방법은 없을까?

정렬 + 스캔으로 O(n log n)에 해결합니다. Interval 문제의 핵심 패턴을 배웁니다.

lightbulb

핵심 개념

Interval

[start, end] 형태의 구간. 회의 시간, 일정, 범위 등

Overlapping

두 구간이 겹침. a.start < b.end and b.start < a.end

article

핵심 내용

Interval 문제는 면접에서 매우 자주 출제됩니다

대표 문제들 • Merge Intervals (겹치는 구간 합치기) • Insert Interval (새 구간 삽입) • Meeting Rooms (회의실 배정) • Non-overlapping Intervals (최소 제거)

겹치는 구간을 합치는 3단계: 1) 정렬 2) 스캔 3) 병합

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])  # start 기준 정렬
    merged = [intervals[0]]
    
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:  # 겹침!
            merged[-1][1] = max(merged[-1][1], end)  # 병합
        else:
            merged.append([start, end])  # 새 구간
    
    return merged

시간: O(n log n) — 정렬이 지배적 공간: O(n) — merged 배열 핵심: 정렬 후 현재 구간의 start ≤ 이전 구간의 end이면 겹침

1,3],[2,6],[8,10],[15,18을 병합 과정을 추적합니다

동시에 진행되는 회의의 최대 개수 = 필요한 회의실 수

방법 1: 정렬 + 두 포인터 시작 시간과 끝나는 시간을 따로 정렬합니다

def minMeetingRooms(intervals: list[list[int]]) -> int:
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)
    
    rooms = 0
    end_ptr = 0
    
    for start in starts:
        if start < ends[end_ptr]:  # 새 회의실 필요
            rooms += 1
        else:                      # 기존 회의실 재사용
            end_ptr += 1
    
    return rooms

시간: O(n log n) — 정렬 공간: O(n) 핵심: start < 가장 빠른 end → 회의실 추가, 아니면 재사용

방법 2: min-heap으로 가장 빨리 끝나는 회의를 추적합니다

import heapq

def minMeetingRooms(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[0])
    heap = []  # 현재 사용 중인 회의실의 종료 시간
    
    for start, end in intervals:
        if heap and start >= heap[0]:  # 가장 빨리 끝나는 회의실 재사용
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)  # 새 회의실
    
    return len(heap)  # 힙 크기 = 동시 사용 회의실 수

heap[0]이 가장 빨리 끝나는 회의. 새 회의 시작이 그보다 늦으면 재사용!

0,30],[5,10],[15,20으로 Heap 풀이를 추적합니다

[5,10] 회의가 끝나고 그 회의실에서 [15,20]이 시작됩니다. 최대 동시 회의 = 2개

Interval 문제를 만나면 이 체크리스트를 따르세요

Interval 문제의 95%는 '정렬 → 스캔 → 조건 분기'로 해결됩니다!

Merge Intervals의 시간 복잡도는?

Meeting Rooms II에서 heap에 저장하는 것은?

1,5],[2,3],[4,6을 merge하면 결과는?

key

핵심 용어

📅

Interval

[start, end] 구간 — 회의/일정/범위

🔀

Merge

겹치는 구간을 하나로 합치기

📊

Sweep Line

시작점/끝점을 이벤트로 처리하는 기법

1️⃣

정렬 기준 선택

start 기준이 기본. 문제에 따라 end 기준도

2️⃣

겹침 조건 정의

a.start < b.end and b.start < a.end

3️⃣

스캔 방향 결정

왼→오 스캔하며 상태 업데이트

4️⃣

자료구조 선택

Heap(동시성), Stack(중첩), 배열(병합)

image

시각 자료

다이어그램: ds-d87

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작