1931

1931번: 회의실 배정

문제

• 회의시간이 $n(1\leq n \leq 10^{5})$개 주어질 때 최대로 진행할 수 있는 회의의 개수?

 

 

$O(nlog\ n)$

남은 회의 중 가장 빨리 끝나는 회의를 우선으로 배정한다

위 알고리즘으로 선택한 회의를 $S$, 최적해를 $O$라 하자
이때 각 집합은 회의가 빨리끝나는 순으로 indexing 되어있다
$$\begin{align*}
&S:= \left \{ p_{1},\ p_{2},\cdot \cdot \cdot, p_{k} \right \}\\
&O:= \left \{ q_{1},\ q_{2},\cdot \cdot \cdot, q_{l} \right \}
\end{align*}$$

이때 어떤 최적해 알고리즘이 $q_{1},\ q_{2},\ ...$순으로 회의를 고른다고 가정하자

$p$ 회의가 끝나는 시간을 $f(p)$로 표기하면

Claim
$$f(p_{i}) \leq f(q_{i}),\ i=1,\ 2,\ ...\ ,\ k,\ k = l$$

$\because$
i) i = 1 일때
trivial

ii) i 일때 준 명제가 성립한다고 가정

(준 알고리즘에서 선택할 수 있는 회의) $\supset$ (최적해 알고리즘에서 선택할 수 있는 회의)
따라서 최적해 알고리즘에서 선택할 수 있는 회의가 있다고 하면 그 회의는 준 알고리즘에서도 고를 수 있다
또한 준 알고리즘은 진행할 수 있는 회의 중 가장 빨리 끝나는 회의를 고르므로 $f(p_{i+1}) \leq f(q_{i+1})$ □

 

c++

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int n;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > meeting;
 
int main()
{
    cin >> n;
    int start, end;
    while(n--){
        cin >> start >> end;
        meeting.push({end, start});
    }
 
    int cnt = 1;
    auto fatest_end_time = meeting.top().first; meeting.pop();
    while(!meeting.empty()){
        auto cur = meeting.top(); meeting.pop();
        if(cur.second >= fatest_end_time){
            fatest_end_time = cur.first;
            cnt++;
        }
    }
 
    cout << cnt << endl;
 
 
    return 0;
}cs

 

python

import sys
from heapq import *
 
n = int(sys.stdin.readline())
h = []
for _ in range(n):
    s, e = map(int, sys.stdin.readline().split())
    h.append((e, s))
 
heapify(h)
e, _ = heappop(h)
res = 1
last = e
while len(h):
    e, s = heappop(h)
    if s >= last:
        last = e
        res += 1
print(res)cs

 

참고

탐욕 알고리즘 분석하기 (Correctness of Greedy Algorithms)