인터벌 스케줄링: 가장 먼저 끝나는 일정을 고르는 이유

같은 자원 하나에서 겹치지 않는 일정을 가장 많이 고를 때에는, 가능한 일정 중 가장 빨리 끝나는 것을 선택합니다. 일찍 비워진 시간은 이후 일정을 받아들일 여지를 줄이지 않습니다.

선수 지식: 배열 정렬·순회·탐욕 선택과 반례

• 종료 시각으로 정렬한 뒤 선택·건너뛰기
• 맞닿은 구간과 겹친 구간 구분하기
• 일정 개수 최대화의 교환 논증 설명하기

최대화하는 값과 구간의 경계를 먼저 정합니다

인터벌 스케줄링은 시작과 종료 시각이 정해진 후보들 중 서로 겹치지 않는 일정을 선택하는 문제입니다. 이 글의 목표는 선택한 일정의 개수를 최대로 만드는 것입니다. 일정의 수익, 중요도, 총 진행 시간은 점수에 포함하지 않습니다. 일정마다 수익이 다르고 수익 합을 최대화한다면 종료 시각만으로 고르는 규칙은 최적성을 보장하지 않습니다. 목표가 무엇인지 고정해야 선택 규칙을 판단할 수 있습니다.

구간은 [start,end)로 해석합니다. 시작 시각은 포함하고 종료 시각은 포함하지 않으므로 [1,4)와 [4,7)은 함께 고를 수 있습니다. 코드에서는 다음 일정의 시작이 마지막 선택의 종료 이상인지 비교합니다. 모든 일정은 유한한 수 시각을 가지고 시작이 종료보다 작아야 합니다. 길이가 0인 구간은 이 예제에서 받지 않습니다. 빈 목록의 답은 빈 목록이며, 첫 일정을 찾기 위한 별도 가짜 시간값도 필요하지 않습니다.

종료 순서로 보고 가능한 일정만 남깁니다

후보가 A=[0,6), B=[1,4), C=[3,6), E=[4,7), H=[8,11)이라고 하겠습니다. 종료 시각으로 정렬하면 B가 가장 앞에 옵니다. B를 선택한 뒤에는 시작이 4보다 작은 후보를 건너뛰고 E를 선택합니다. 이어서 H를 선택하므로 결과는 B, E, H 세 개입니다. 시작이 가장 빠른 A부터 고르면 B와 E를 모두 놓치므로 시작 순서가 같은 의미를 갖지 않습니다.

후보를 건너뛸 때 마지막 종료를 갱신하지 않는 점도 중요합니다. 마지막 종료는 지금 본 후보의 종료가 아니라 실제 선택한 일정의 종료입니다. 제외된 긴 일정으로 이 값을 덮어쓰면 뒤의 유효한 일정을 부당하게 놓칠 수 있습니다.

최적해의 첫 일정을 바꾸어도 개수가 줄지 않습니다

최대로 많은 일정을 고른 어떤 해의 첫 일정을 X, 전체 후보 중 가장 빨리 끝나는 일정을 G라고 하겠습니다. G의 종료는 X의 종료보다 늦지 않습니다. 그 해에서 X를 G로 바꾸어도 X 뒤에 가능했던 일정들은 여전히 가능합니다. 뒤 일정의 시작은 X의 종료 이상이었고, G는 그보다 늦게 끝나지 않기 때문입니다. 따라서 G를 포함하는 최적해도 존재합니다.

G를 고른 뒤에는 G의 종료 이전에 시작하는 후보를 제외하고 같은 문제를 반복합니다. 매 단계의 선택이 남은 최적해의 첫 일정을 대신할 수 있으므로 선택 수의 최적성이 이어집니다. “짧은 일정이 더 많이 들어갈 것 같다”는 직감과 구분하세요. 길이가 가장 짧은 구간도 가운데를 차지해 양쪽의 두 일정을 동시에 막을 수 있습니다. 이 증명에서 필요한 비교는 일정 길이가 아니라 종료 시각입니다.

동률과 원본 순서의 계약을 분명히 합니다

종료 시각이 같은 후보는 시작 시각, 마지막으로 입력 위치를 비교하여 처리 순서를 정합니다. 종료 동률의 어느 후보를 고르더라도 이후에 남기는 시간의 경계는 같지만, 선택된 ID를 재현하려면 동률 규칙이 필요합니다. 이 예제는 원본 목록을 복사해 정렬하므로 화면이나 다른 계산에서 쓰는 입력 순서를 변경하지 않습니다. 반환 목록에는 선택한 일정 객체가 들어가며 객체 자체도 변경하지 않습니다.

후보 N개를 정렬한 뒤 한 번 순회하므로 일반적인 비교 정렬 기준 시간은 O(N log N), 복사·선택 결과를 위한 공간은 O(N)입니다. 이미 종료 시각 순으로 정렬되어 있고 그 계약을 믿을 수 있다면 선택 단계만 O(N)입니다. 학습 중에는 작은 후보 집합의 모든 부분집합을 열거하여 최대 개수를 비교해 보세요. 다만 같은 최대 개수라도 여러 선택 목록이 가능하므로, 다른 목록이라는 이유만으로 오답이라 판단하지 말고 겹침 여부와 개수를 먼저 확인해야 합니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function intervalScheduling(jobs) {
  if (!Array.isArray(jobs)) throw new TypeError('일정 배열이 필요합니다.');
  const sorted = Array.from(jobs, (job,index) => {
    if (!job || typeof job.id !== 'string' || !Number.isFinite(job.start)
        || !Number.isFinite(job.end) || job.start >= job.end) {
      throw new RangeError('일정은 문자열 id와 시작 < 종료인 유한 구간이 필요합니다.');
    }
    return { job, index };
  }).sort((a,b) => a.job.end-b.job.end || a.job.start-b.job.start || a.index-b.index);
  const result = [];
  for (const { job } of sorted) {
    if (result.length === 0 || job.start >= result[result.length-1].end) result.push(job);
  }
  return result;
}

const jobs = [
  {id:'A',start:0,end:6}, {id:'B',start:1,end:4},
  {id:'C',start:3,end:6}, {id:'E',start:4,end:7},
  {id:'H',start:8,end:11}
];
console.log(JSON.stringify(intervalScheduling(jobs).map(job => job.id)));
console.log(JSON.stringify(intervalScheduling([])));

node algorithm-interval-scheduling-greedy.mjs

["B","E","H"]
[]

비용과 적용 범위

일정 N개, 비교 정렬 기준 시간 O(N log N), 입력 복사와 결과 저장 공간 O(N)입니다. 종료 순 정렬을 이미 보장하면 선택 순회만 O(N)입니다. 양의 길이인 반열린 구간, 자원 하나, 동일한 일정 가치에서 선택 개수를 최대화합니다.

직접 확인해 보기

A=[0,5), B=[1,2), C=[2,3), D=[3,5)에서 어떤 일정을 고를까요? B와 C는 왜 함께 선택할 수 있을까요?

함께 읽을 글

• 완전탐색과 쌍 비교: 중복 없는 후보 열거와 순위 계산 — 작은 일정의 가능한 부분집합과 탐욕의 선택 수를 비교하는 연습에 도움이 됩니다.
• JavaScript 최소 힙 구현: 우선순위 큐의 push·pop과 비교 함수 — 일정 개수 최대화와 우선순위 큐의 작업 처리 순서가 서로 다른 목표임을 비교합니다.

참고 자료

• Competitive Programmer’s Handbook — 6.2 Scheduling — 종료 시각 우선 선택으로 겹치지 않는 일정의 개수를 최대화하는 원리.