11000

11000번: 강의실 배정

문제

• $n(1 \leq n \leq 2\cdot 10^{5}$개의 수업을 가능하게 하기 위한 최소 강의실의 개수?
• 강의시간은 $[s,\ e)$ 이다(강의시간에 시각 e 는 포함하지 않는다)

 

$O(nlog\ n)$

빨리 시작하는 순서로 고려한다
기존 강의실에 배정할 수 있으면 배정하고 못한다면 새로운 강의실을 만든다
위의 알고리즘을 진행하면서 강의실을 가장 많이 사용할 때의 강의실 수가 최적해이다

위 그림에서 실선 t 와 만나는 강의의 개수를 $U(t)$라고 하자

Claim
준 알고리즘의 해는 (수업이 최대로 겹칠때 겹치는 수업의 수) 이다.

$\because$
준 알고리즘이 시작시간이 $s$인 모든 강의의 강의실을 배정을 마쳤다고 하자
(예를 들어, 위 그림에서 $c \rightarrow d$순으로 배정했다고 하면 $c$가 아닌 $d$ 배정을 마쳤을 때)
이때 사용중인 강의실의 수는 $U(s)$
(수업이 최대로 겹칠때 겹치는 수업의 수) =$\mathrm{max(\left \{ U(s)|\mathrm{s\in \mathrm{all\ classes}} \right \})}$□

 

한편, 시각 t 에 수업하는 수업들은 같은 강의실에서 강의하지 못한다
즉, 최적해는 (수업이 최대로 겹칠때 겹치는 수업의 수) 이상이어야 한다

준 알고리즘은 최적해가 갖을 수 있는 값 중 가장 작은 값을 해로 갖으므로 최적해 알고리즘이다

c++

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > subject;
priority_queue<int, vector<int>, greater<> > classroom;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int n;
    cin >> n;
    int start, end;
    while(n--){
        cin >> start >> end;
        subject.push({start, end});
    }
 
    classroom.push(subject.top().second); subject.pop();
    while(!subject.empty()){
        tie(start, end) = subject.top(); subject.pop();
        int last = classroom.top();
        if(last <= start) classroom.pop();
        classroom.push(end);
    }
 
    cout << classroom.size() << endl;
 
    return 0;
}cs

 

python

import sys
from heapq import *
 
n = int(input())
subject = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
heapify(subject)
 
room = [0]
while(subject):
    s, e = heappop(subject)
    end = room[0]
    if end <= s: heappushpop(room, e)
    else: heappush(room, e)
print(len(room))cs

 

 

참고

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