[Algorithm/C] BOJ.1931 회의실배정
문제
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.
예제 입력 1 복사
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
예제 출력 1 복사
4
힌트
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
출처: <https://www.acmicpc.net/problem/1931>
/*
Problem : 회의실배정
Writer : JaeIn Mun
Final revision : 2018.04.20
Reference : http://jaeonysos.tistory.com
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct _Meeting {
int begin, end;
} Meeting;
int comp_end(const void *a, const void *b) {
const Meeting *m, *n;
m = (const Meeting *)a;
n = (const Meeting *)b;
if (m->end < n->end) {
return -1;
}
else if (m->end == n->end) {
return 0;
}
else {
return 1;
}
}
int main(void) {
int n;
scanf("%d", &n);
int len = 0;
Meeting tmp; // variable for bubble sort
int ans = 0;
int nowTime = 0;
Meeting a[100000] = { 0, };
for (int i = 0; i < n; i++) {
scanf("%d %d", &a[i].begin, &a[i].end);
}
// quick sort
qsort(a,n,sizeof(Meeting),comp_end);
/*printf("1st sort\n");
for (int i = 0; i < n; i++) {
printf("begin : %d\nend : %d\n", a[i].begin, a[i].end);
}
*/
for (int i = n - 1; i > 0; i--) {
for (int j = n - 1;j>1; j--) {
if (a[j].end != a[j].end) {
break;
}
else if (a[j].begin < a[j - 1].begin) {
tmp = a[j - 1];
a[j - 1] = a[i];
a[j] = tmp;
}
}
}
/*printf("2nd sort\n");
for (int i = 0; i < n; i++) {
printf("begin : %d\nend : %d\n", a[i].begin, a[i].end);
}*/
for (int i = 0; i < n; i++) {
if (nowTime <= a[i].begin) {
nowTime = a[i].end;
ans += 1;
}
}
printf("%d\n", ans);
return 0;
}
*Greedy Algorithm, 시간초과 떠서 질문 올려놓은 상태