2.12.1 Interval Selection

개념

그리디는 각 단계에서 정한 기준에 따라 하나를 선택하고, 그 선택을 유지하며 답을 만드는 방법입니다. 최적해는 문제에서 요구하는 값을 가장 크게 또는 가장 작게 만드는 답입니다. 그리디를 사용하려면 지금의 선택을 포함하는 최적해가 있다는 근거가 필요합니다.

문제 유형에 따른 선택 기준

유형이 같아도 조건이나 목적이 바뀌면 기준이 달라집니다. 구간의 개수를 최대화하는 문제와 구간마다 주어진 보상의 합을 최대화하는 문제는 구별해야 합니다. 보상이 있다면 늦게 끝나는 구간 하나의 보상이 짧은 구간 여러 개의 보상보다 클 수 있습니다.

동전도 큰 것부터 고르는 방법이 항상 성립하지는 않습니다. 단위가 $1$, $3$, $4$이고 목표 금액이 $6$이면 큰 동전부터 고를 때 $4+1+1$로 $3$개, $3+3$으로 만들 때는 $2$개입니다. 반면 $1$, $5$, $10$처럼 각 단위가 바로 아래 단위의 정수배이면 작은 동전 여러 개를 큰 동전 하나로 바꾸어 개수를 줄일 수 있습니다. 이 경우 큰 단위부터 선택하는 근거가 됩니다.

종료 시각이 빠른 구간 선택

한 장소에서 활동을 겹치지 않게 진행하며 최대한 많이 선택하려고 합니다. 가장 빨리 끝나는 활동을 고르면 다음 활동을 시작할 수 있는 시각을 가장 앞당길 수 있습니다.

종료 시각이 빠른 순서로 정렬한 뒤, 직전에 고른 활동의 종료 시각 이상에서 시작하는 활동을 선택합니다. 선택했다면 마지막 종료 시각을 갱신합니다.

활동이 $(1,10)$, $(2,3)$, $(3,4)$, $(5,7)$이면 종료 시각 순서는 $(2,3)$, $(3,4)$, $(5,7)$, $(1,10)$입니다. 앞의 세 활동은 순서대로 선택할 수 있어 답이 $3$입니다. 시작 시각만 보고 $(1,10)$을 먼저 고르면 한 개만 선택하게 됩니다.

첫 선택을 바꾸어도 되는 이유

활동을 최대한 많이 선택한 어떤 최적해를 잡고, 그 첫 활동을 $A$라고 합니다. 전체 활동 중 가장 빨리 끝나는 활동을 $G$라고 하면, $G$의 종료 시각은 $A$의 종료 시각 이하입니다.

최적해에서 $A$를 $G$로 바꾸어도 이후 활동은 그대로 진행할 수 있습니다. 이후 활동은 원래 $A$가 끝난 뒤 시작하므로, 더 일찍 또는 같은 시각에 끝나는 $G$와도 겹치지 않기 때문입니다. 선택한 개수도 같습니다. 따라서 $G$를 첫 활동으로 포함하는 최적해가 존재합니다.

$G$와 겹치는 활동을 제외하면 남은 문제도 같은 형태입니다. 남은 활동에서 다시 가장 빨리 끝나는 것을 선택하는 과정을 반복할 수 있습니다. 이처럼 최적해의 선택을 그리디의 선택으로 바꿔도 답이 나빠지지 않음을 보이는 방법이 교환 논증입니다.

복잡도

활동 수를 $N$이라고 합니다.

예제

문제

활동의 시작 시각과 종료 시각이 주어진다. 겹치지 않게 선택할 수 있는 활동의 최대 개수를 구하여라. 앞 활동의 종료 시각에 다음 활동을 시작할 수 있다.

입력

첫째 줄에 활동 수 $N$이 주어진다. $1\le N\le100$이다.

다음 $N$개 줄에 활동의 시작 시각 $s$와 종료 시각 $e$가 공백을 사이에 두고 주어진다. $1\le s<e\le1\,000$이다.

출력

선택할 수 있는 활동의 최대 개수를 출력한다.