11000 - 강의실 배정
본문
수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.
김종혜 선생님한테는
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉,
수강신청 대충한 게 찔리면, 선생님을 도와드리자!
입력
첫 번째 줄에
이후
출력
강의실의 개수를 출력하라.
제한
시간 제한 | 메모리 제한 |
---|---|
1sec | 256MB |
풀이
모든 수업을 배정하기 위한 최소 강의실의 개수를 구하는 문제이다. 강의실에 수업을 하나하나 넣어보면 쉽게 해결할 수 있는 문제이다. 수업이 끝나면 그 강의실은 비워둔 채로 있다가, 다른 수업이 시작한다하면 빈 강의실에 배정하면 된다. 만약 모든 강의실에서 수업 중이라면 강의실은 하나 더 만들어서 배정하면 된다. 빈 강의실은 없어지지 않으므로, 결과적으로는 새로 만들어진 강의실의 개수를 세면 될 것 같다.
배열을 통해 문제를 해결할 수 있다. 배열의 칸들을 각각 하나의 강의실로 생각하고, 수업이 끝나 빈 강의실에 새로운 수업을 넣으면 된다. 수업을 넣어야 하는데 빈 강의실이 없다면 배열의 칸을 하나 늘리는 것으로 강의실을 만들어낼 수 있다. 그렇게 한다면 최종적으로 만들어진 배열의 길이가 문제에서 원하는 답이 된다. 문제는 강의실의 관리이다. 수업이 끝난 시간마다 강의실을 비워야하고, 빈 강의실을 찾아가는 과정 또한 배열 탐색을 거쳐야하므로
이 점은 우선순위 큐를 이용하면 문제를 쉽게 해결할 수 있다. 강의실을 만들어야할 상황이라면 결과값에
- 참고 알고리즘 : 우선순위 큐
코드
사용 언어 : C
최종 수정일 : 2024 / 5 / 30
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
typedef struct Class {
int s, e;
} CS;
#define MAX_IDX 200000
const int NONE = -1;
int cmp(CS* a, CS* b) {
if (a->s != b->s) {
return a->s > b->s;
} else {
return a->e > b->e;
}
}
int n;
CS arr[MAX_IDX];
int priority_queue[2 * MAX_IDX + 10];
int top = 0;
void insert(int x) {
priority_queue[++top] = x;
int i = top;
while (i != 1 && x < priority_queue[i / 2]) {
int a = priority_queue[i / 2];
priority_queue[i / 2] = x, priority_queue[i] = a;
i /= 2;
}
return;
}
int pop() {
if (top == 0) {
return 0;
}
int retval = priority_queue[1];
priority_queue[1] = priority_queue[top--];
int i = 1, tp = 2;
while (tp < top) {
tp += (priority_queue[tp] > priority_queue[tp + 1]);
if (priority_queue[i] <= priority_queue[tp]) {
break;
}
int a = priority_queue[tp];
priority_queue[tp] = priority_queue[i], priority_queue[i] = a;
i = tp, tp *= 2;
}
if (tp == top && priority_queue[i] > priority_queue[tp]) {
int a = priority_queue[tp];
priority_queue[tp] = priority_queue[i], priority_queue[i] = a;
}
return retval;
}
int head() {
if (top == 0) {
return NONE;
} else {
return priority_queue[1];
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int a, b;
scanf("%d %d", &a, &b);
arr[i] = (CS){a, b};
}
qsort(arr, n, sizeof(CS), cmp);
int retval = 1;
insert(arr[0].e);
/* solve() */
for (int i = 1; i < n; ++i) {
if (arr[i].s < head()) {
++retval;
} else {
pop();
}
insert(arr[i].e);
}
printf("%d", retval);
return 0;
}