Frame
Range
구간을 정렬해 겹침 여부를 판단하고 병합·분할하는 범위 처리 패턴과 대표 문제 전략을 정리
Oct 22, 2025
- 주어진 구간들을 병합하는 문제.
- 구간을 begin 값으로 오름차순으로 정렬하고
- mreged interval의 end 값과 current interval의 begin 값을 비교하여 병합 가능한 구간을 찾는 방법
병합 구간의 마지막 값의 end 값 < 현재 구간의 begin 값
current interval ----------------- | | ------------ | | last in merged intervals현재 구간의 begin 값 < 병합 구간의 마지막 값의 end 값
current interval ----------------- | | ------------ | | last in merged intervals
[merged.at(-1[0], Math.max(merged.at(-1)[1], current.at(1)))]var merge = function(intervals) { intervals.sort((a,b) => a[0] - b[0]);
const stack = [];
for (const interval of intervals) { if (stack.length === 0 || stack.at(-1)[1] < interval[0]) { stack.push(interval) } else { stack.at(-1)[1] = Math.max( stack.at(-1)[1], interval[1] ) } } return stack;};- 구간을 시작 시간 기준으로 오름차순 정렬
- 이전 구간의 종료시간이 다음 구간의 시작시간보다 크다면 겹침 발생.
intervals.sort((a,b) => a[0] - b[0]);
const stack = [];
for (const interval of intervals) { if (stack.length === 0 || stack.at(-1)[1] < interval[0]) { stack.push(interval) } else { stack.at(-1)[1] = Math.max( stack.at(-1)[1], interval[1] ) } } return stack;};