💡 자료 구조/그리디 알고리즘/우선순위 큐/정렬
Memory 4316KB Time 84ms Code Length 781B
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
42
43
44
45
46
47
48
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct info {
int start;
int end;
};
bool cmp(const info & a, const info &b) {
if (a.start < b.start) {
return true;
}
else if (a.start == b.end) {
if (a.end < b.end) {
return true;
}
}
return false;
}
int main() {
int n;
scanf("%d", &n);
vector<info> v;
priority_queue<int, vector<int>, greater<int>> endtime;
for (int i = 0; i < n; i++) {
info tmp;
scanf("%d %d", &tmp.start, &tmp.end);
v.push_back(tmp);
}
// 기본적으로 첫번째 원소 기준 정렬임.
sort(v.begin(), v.end(), cmp);
for (int i = 0; i < v.size(); i++) {
endtime.push(v[i].end);
if (endtime.top() <= v[i].start) endtime.pop();
}
printf("%d", endtime.size());
}
이 코드는 회의실 배정 문제를 해결하는 프로그램이다.
- info 구조체는 회의 시작 시간과 끝나는 시간을 저장한다.
- cmp 함수는 회의의 시작 시간을 기준으로 오름차순으로 정렬하기 위한 비교 함수이다.
- main 함수에서는 회의의 개수를 입력받고, 각 회의의 시작 시간과 끝나는 시간을 입력받아 벡터에 저장한다.
- 그 후, 시작 시간을 기준으로 벡터를 정렬한다.
- 우선순위 큐인 endtime에 각 회의의 끝나는 시간을 넣어가면서, 현재 회의의 시작 시간과 가장 빨리 끝나는 회의의 끝나는 시간을 비교하여 회의실을 배정한다.
- 마지막으로, endtime의 크기를 출력하여 최대로 배정할 수 있는 회의실의 개수를 구한다.
