[백준 - 1931] 회의실 배정 - C++, Python

분류: 그리디 /

 

문제

문제 링크

문제 설명

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2³¹-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

풀이

- C++

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    pair<int, int> task[N];
    for(int i=0; i<N; i++) {
        int s, e; cin >> s >> e;
        task[i] = {e, s};
    }
    sort(task, task+N);
    int ans = 0, t = 0;
    for(const auto &[e, s]:task) {
        if(s < t) continue;
        t = e;
        ans++;
    }
    cout << ans;
}

 

- Python

import sys
from operator import itemgetter
readline = sys.stdin.readline
n = int(readline())
tasks = sorted(
    [tuple(map(int, readline().split())) for _ in range(n)], 
    key = itemgetter(1,0)
)

ans = last = 0
for start, end in tasks:
    if start >= last:
        last = end
        ans += 1
print(ans)

 

대표적인 그리디 문제로 `구간 스케줄링(Interval scheduling)`문제다. 

가장 이른 종료 시간을 그리디하게 선택하는 것이 최적해다.

 

귀류법을 이용해 가장 이른 종료 시간을 선택하는 것 보다 더 많은 회의를 선택하는 방법이 없음을 증명할 수 있다.

 

편의를 위해 `현재 시간이 t일때 시작시간이 t 이상인 모든 회의 중 가장 먼저 끝나는 회의를 A`, `가장 먼저 끝나지 않는 회의를 B`라 하자.

 

명제: `A`를 선택하는 것이 최적이다.

명제를 거짓이라 가정: `B`를 선택했을 때 `A`보다 더 많은 회의를 선택 할 수 있다.

`B`를 선택했을 때 선택 할 수 있는 모든 회의는 `A`를 선택했을 때에도 선택할 수 있다. 즉 `B` 이후 선택은 `A`이후 선택의 부분 집합이다.

따라서 가정이 거짓이므로 `A`를 선택했을 때보다 더 나은 선택지는 없다.

 

 

이때 정렬 조건을 `종료 시간 오름차순` -> `시작 시간 오름차순`으로 해야한다.

시작 시간 오름차순은 시작 시간과 종료 시간이 같은 경우 필요하다.

예를 들어 A(1, 2), B(2, 2) 두개의 태스크가 있을때 `A -> B`는 가능 하지만 `B -> A`는 불가능하다.