겹치는 구간 병합하기
맞닿거나 겹치는 범위를 합칩니다
겹치는 구간 병합하기은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
병합의 목표
많은 구간이 주어졌을 때 서로 맞닿거나 겹치는 구간을 병합하여 겹치지 않는 구간의 수를 최대한 줄이고 싶습니다. 🧩
두 구간이 겹치는 경우
한 구간의 시작점이 다른 구간의 끝점보다 앞에 있으면 두 구간은 겹칩니다. 시작점으로 정렬한 뒤에는 다음 구간의 시작점이 현재 끝점 이하인지 확인하면 됩니다.
항상 먼저 정렬하기
구간이 순서대로 있어야 왼쪽에서 오른쪽으로 병합할 수 있으므로 먼저 시작점으로 정렬하십시오. 이것이 전체 훑기의 기반입니다.
intervals.sort(key=lambda x: x[0])현재 구간 유지하기
정렬된 목록을 훑으면서 병합 중인 하나의 현재 구간을 유지합니다. 새 구간은 현재 구간을 확장하거나 새로운 구간을 시작합니다.
겹치면 확장하기
다음 시작점이 현재 구간 안에 있으면 두 구간은 겹치므로 현재 구간의 끝점을 두 끝점 중 더 큰 값으로 늘립니다.
cur_end = max(cur_end, end)끝점의 최댓값 사용하기
새 끝점에는 항상 최댓값을 사용하십시오. 긴 구간 안에 포함된 짧은 구간 때문에 이미 만든 범위가 줄어들어서는 안 됩니다.
닫고 새로 열기
다음 시작점이 현재 끝점을 지나면 간격이 생긴 것입니다. 완성된 구간을 답에 추가하고 새로운 현재 구간을 시작하십시오.
result.append([cur_start, cur_end])마지막 구간을 잊지 않기
반복문은 마지막 구간을 만들지만 답에 추가하지는 않습니다. 반복문이 끝난 뒤 마지막 현재 구간을 append하여 잃어버리지 않도록 하십시오.
맞닿으면 겹치는 것으로 셉니다
[1, 3]과 [3, 5]를 합쳐야 하는지 판단해 보십시오. 보통은 합치므로 start <= cur_end를 사용합니다. 이 경계 규칙은 문제를 읽고 확인하십시오.
전체 스윕
정렬한 뒤 한 번만 순회하면 합쳐진 모든 구간을 얻을 수 있으므로, 전체 방법의 시간 복잡도는 정렬에 필요한 O(n log n)과 선형 스윕을 합쳐 O(n log n)입니다.
for s, e in intervals[1:]:
if s <= cur_end:
cur_end = max(cur_end, e)
else:
result.append([cur_start, cur_end]); cur_start, cur_end = s, e일반적인 활용
달력과 예약 시스템에서는 구간을 합쳐 바쁜 시간대를 하나로 만들면 실제 여유 시간을 확인할 수 있습니다. 많은 대회 문제도 이와 같은 형태를 숨겨 두고 있습니다.
빠른 확인
시작 시점을 기준으로 정렬한 뒤 구간을 합칩니다.
복습
시작 시점을 기준으로 정렬하고 현재 구간을 유지한 다음, 겹치면 최댓값으로 확장하고 빈틈이 생기면 현재 구간을 추가한 뒤 새로 시작합니다. 마지막 append를 잊지 마십시오. 🚀
자주 묻는 질문
“겹치는 구간 병합하기” 강의는 무료인가요?
네 — “겹치는 구간 병합하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“겹치는 구간 병합하기”에서 뭘 배우나요?
맞닿거나 겹치는 범위를 합칩니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“겹치는 구간 병합하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.