구간 스케줄링(Interval Scheduling)은 한정된 자원 위에서 서로 겹치지 않는 최대 개수의 작업을 선택하는 최적화 문제입니다. 이는 컴퓨터 과학의 고전적인 조합 최적화(Combinatorial Optimization) 영역에 속하며, 자원 배분(Resource Allocation)과 작업 스케줄링(Task Scheduling) 시스템의 핵심 설계 기반이 됩니다. 현대의 IT 인프라 스트럭처 내에서 클라우드 컴퓨팅의 인스턴스 할당 효율성이나 실시간 데이터 처리 파이프라인의 처리량(Throughput) 극대화를 위해 이 알고리즘의 원리가 광범위하게 응용되고 있습니다. 특히 시간 복잡도의 효율성을 보장해야 하는 대규모 시스템에서 구간 스케줄링의 그리디 전략은 결정적인 성능 우위를 점하는 요소로 평가받습니다.
1. 구간 스케줄링(Interval Scheduling)의 그리디 알고리즘 작동 원리
구간 스케줄링을 해결하기 위한 가장 효율적인 전략은 탐욕 알고리즘(Greedy Algorithm)입니다. 그리디 기법은 매 순간의 선택에서 현재 상황에 가장 최적이라고 판단되는 해답을 선택하여 최종적인 해답에 도달하는 방식입니다. 구간 스케줄링 문제에서 그리디 전략의 핵심은 '종료 시간(Finish Time)'을 기준으로 정렬하는 것입니다. 이는 전체 구간 중에서 가장 먼저 끝나는 작업을 우선적으로 선택하는 방식이며, 이를 통해 남은 가용 시간(Remaining Available Time)을 최대한 확보할 수 있습니다. 수학적으로 증명된 바에 따르면, 종료 시간을 기준으로 정렬한 뒤 겹치지 않는 구간을 선택해 나가는 방식은 언제나 전체 최적해(Global Optimum)를 보장합니다.
구체적인 작동 메커니즘을 살펴보면 다음과 같습니다. 먼저 모든 작업 구간을 그들의 종료 시간 $f_i$에 따라 오름차순(Ascending Order)으로 정렬합니다. 종료 시간이 동일할 경우에는 시작 시간(Start Time)의 순서는 결과에 영향을 미치지 않으나, 일반적으로 일관성을 위해 시작 시간 순으로 정렬을 수행하기도 합니다. 이후 첫 번째 작업을 선택한 뒤, 해당 작업의 종료 시간보다 늦게 시작하는 가장 빠른 작업을 다음 작업으로 선택하는 과정을 반복합니다. 이러한 방식은 마치 "가장 일찍 끝나는 수업을 먼저 들어야 다음에 들을 수 있는 강의 후보군이 많아지는 것"과 같은 논리입니다. 이 과정의 시간 복잡도는 정렬 단계에서의 $O(N \log N)$에 지배되며, 정렬 이후의 탐색 과정은 선형 시간인 $O(N)$ 내에 완료됩니다. 따라서 대량의 데이터 세트에서도 매우 빠른 처리 속도를 보여줍니다.
비전공자의 이해를 돕기 위해 비유하자면, 그리디 알고리즘은 마치 뷔페에서 가장 접시가 빨리 비워질 음식부터 담아 자리를 확보하는 전략과 유사하다고 할 수 있습니다. 만약 시작 시간이 빠른 순서나 기간이 짧은 순서로 선택할 경우, 매우 길게 이어지는 하나의 구간이 다른 여러 개의 짧은 구간들을 가로막아 전체 효율이 떨어지는 '국소 최적해(Local Optimum)'의 함정에 빠질 수 있습니다. 하지만 종료 시간 기준의 선택은 증명된 탐욕적 선택 속성(Greedy Choice Property)과 최적 부분 구조(Optimal Substructure)를 완벽히 만족하므로, 가장 논리적이고도 강력한 해결책이 됩니다.
2. 구간 스케줄링(Interval Scheduling)의 단계별 구현 가이드 및 코드 분석
실제 프로그래밍 환경에서 구간 스케줄링을 구현하기 위해서는 데이터 구조의 정의와 정렬 인터페이스의 활용이 무엇보다 중요합니다. 우선 각 구간을 나타내는 구조체(Structure) 또는 클래스(Class)를 정의해야 합니다. 이 객체는 시작 시간(start)과 종료 시간(end)이라는 두 개의 속성을 반드시 포함해야 합니다. 이후 프로그래밍 언어에서 제공하는 표준 라이브러리의 정렬 함수를 사용하여 종료 시간을 기준으로 전체 배열을 정렬합니다. 자바(Java)의 경우 Comparator 인터페이스를 사용하고, 파이썬(Python)의 경우 람다(Lambda) 식을 활용하여 정렬 기준(Key)을 설정하는 것이 일반적인 관례(Best Practice)입니다.
정렬이 완료된 이후에는 선택된 작업을 추적할 변수를 설정합니다. 일반적으로 '마지막으로 선택된 작업의 종료 시간'을 저장하는 변수(last_finish_time)를 0 또는 음의 무한대로 초기화한 뒤, 전체 리스트를 순회(Iterate)합니다. 현재 검사 중인 구간의 시작 시간이 last_finish_time보다 크거나 같다면, 해당 구간은 이전 작업과 겹치지 않는 것으로 간주하여 선택 목록에 추가하고 last_finish_time을 현재 작업의 종료 시간으로 갱신합니다. 이 과정을 반복하면 최종적으로 선택된 작업들의 집합이 구성됩니다. 이 로직은 불필요한 계산을 배제하고 단 한 번의 순회로 결과를 도출하므로 극도의 효율성을 자랑합니다.
// Java 기반의 구간 스케줄링 핵심 로직 예시
public int selectMaxIntervals(List<Interval> intervals) {
// 1. 종료 시간 기준 오름차순 정렬
Collections.sort(intervals, (a, b) -> a.end - b.end);
int count = 0;
int lastEndTime = 0;
for (Interval interval : intervals) {
// 2. 현재 구간의 시작 시간이 마지막 종료 시간 이후인지 확인
if (interval.start >= lastEndTime) {
count++;
lastEndTime = interval.end; // 종료 시간 갱신
}
}
return count;
}
추가적으로 실무에서는 단순히 개수를 세는 것뿐만 아니라, 선택된 구간들의 인덱스나 구체적인 정보를 반환해야 하는 경우가 많습니다. 또한, 동적 계획법(Dynamic Programming)으로 해결해야 하는 '가중치가 있는 구간 스케줄링(Weighted Interval Scheduling)'과의 차이점을 명확히 인지해야 합니다. 가중치가 없는 경우에는 지금 설명한 그리디 방식이 최적이지만, 각 구간마다 중요도나 이익이 다를 경우에는 그리디가 아닌 $O(N \log N)$의 DP 알고리즘을 사용해야 합니다. 따라서 개발자는 문제의 요구사항을 명확히 분석하여 그리디 전략의 적용 가능 여부를 판단하는 혜안을 가져야 합니다.
3. 실무 경험 및 개발자로서의 경험담
제가 2년 전쯤 한 물류 스타트업에서 배송 차량의 배차 시스템 리팩토링 업무를 맡았었어요. 당시 시스템은 단순히 배송 시작 시간이 빠른 순서대로 차를 배정하고 있었죠. 그러다 보니 새벽에 일찍 시작해서 오후 늦게 끝나는 장거리 노선 하나가 차량을 점유해 버리면, 그 사이에 처리할 수 있는 짧은 노선 서너 개가 전부 취소되는 비효율이 발생하더라고요.
사실 회사에서 크게 신경 쓰지 않았고 그러려니 해서 다들 관심을 갖지 않았는데 저는 그런 게 계속 신경이 쓰이더라고요 그러다가 개발자 모임에서 만났던 한 시니어 개발자분이 근처에 오셨다고 해서 잠깐 차를 마시러 갔었는데, 그 때 그냥 요즘 근황 이야기 하면서 이런 게 있는데 좀 신경 쓰이더라, 다들 별로 관심이 없는 거 같고... 그랬더니 "그리디의 정석인 종료 시간 정렬을 써봤냐"라고 툭 던지신 한마디에 머리를 한 대 맞은 기분이었어요.
알고 보니 정말 정렬 기준 하나 설정하는 사소한 로직 차이 때문이었더라고요. 코드를 수정하고 나니 동일한 차량 대수로도 하루 처리 물동량이 15%나 증가했었죠. 다들 비효율이 발생하는 건 알고 있었지만 이래저래 고민해 봐도 딱히 답이 없는 거 같아서 그냥 내버려 뒀었다고 하네요. 덕분에 팀장님께 포인트하나 따냈었답니다.
- 그리디 전략: 구간 스케줄링의 최적해는 종료 시간(Finish Time) 기준 정렬로 구합니다.
- 시간 복잡도: 정렬에 의해 $O(N \log N)$이 결정되며 탐색은 $O(N)$입니다.
- 주의사항: 시작 시간이나 소요 시간 기준 정렬은 최적해를 보장하지 못합니다.