백준 11000 강의실 배정

작성일 | In |

Problem : 강의실 배정

유형 : 그리디

문제 해석

  • 강의실을 최소로 이용하여 모든 수업을 가능하게 만들어라

문제 재해석

  • 사용중인 강의실은 사용할 수 없다.
  • 수업이 끝난 직후 바로 이어 쓸 수 있다.

해결 전략

  • 그리디 하게 접근한다.
  • 회의실 배정에서 살짝 바뀐 문제이다. 수업이 가장 일찍 끝난 (최선의 선택) 강의실을 배정 시켜 나간다.

설계, 구현

  • 모두 사용중 이라면, 강의실을 추가한다.
  • 사용중 이지 않은 강의실이 여러개 있다면, 가장 빨리 수업이 끝난 강의실을 배정 시킨다.

주의할 점

  • 없음

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define pp pair<int,int>
#define start_time first
#define end_time second

using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;
int n;
pp _class[200002];

void Solve() {
    for (int i = 0; i < n; ++i) {
        if (!pq.empty()) {
			int fastest_fin = pq.top();
			if (fastest_fin <= _class[i].start_time) pq.pop();
		}
        pq.push(_class[i].end_time);
	}
    cout << (int)pq.size() << "\n";
}

void Input() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> _class[i].start_time >> _class[i].end_time;
    }
    sort(_class, _class + n);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

피드백

  • priority queue의 데이터들은 const 형이다.
  • 그러므로 int &n = top() 과 같은 방법이 불가능하다.