Easy is Perfect

[백준] 1931번 C/C++ 풀이 _ 회의실배정

  • melonicedlatte
  • Feb 02, 2018


문제 : https://www.acmicpc.net/problem/1931 

회의실배정 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB126953419260529.083%

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

예제 입력 

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 

4

힌트

(1,4) , (5,7), (8,11) , (12,14) 를 이용할 수 있다.

출처

알고리즘 분류



- 문제를 읽어보면 회의 수는 100,000 개 이다.
O(n2) 알고리즘으로는 시간 초과가 난다. 
적어도 O(nlogn) 정도의 알고리즘이 필요해보인다. 

회의 시간에 대한 문제는 그리디 알고리즘의 대표적인 문제이다. 
회의 시간이 끝나는 시간을 기준으로 정렬을 한 후에,
현재 기준에서 가능한 회의 가장 회의가 빨리 끝나는 놈을 고르면 된다. 

회의 시간이 끝나는 시간을 기준으로 정렬하면 O(nlogn) 의 시간이 소요된다. 


문제가 풀리지 않아서 계속 고민하다가 다른 사람의 후기를 읽어보니, 
아래와 같은 케이스가 들어오면 원하는 해답이 나오지 않는 것이 문제였다. 

8 8
7 8  

현실에서는 회의라는게 8 8 같은 케이스는 없다고 생각해도 되지만,
이번 문제의 input 에는 해당 사항이 필요한 것 같았다. 

아래의 경우에는 1개가 카운트되지만 
8 8 
7 8
아래의 경우에는 2개가 카운트 된다.
7 8
8 8 

따라서, 먼저 회의가 끝나는 시간에 대하여 정렬한 다음에,
끝나는 시간이 같은 회의들을 회의가 시작하는 시간에 대하여 정렬하는 것이 필요하다. 

모든 회의의 끝나는 시간이 같다고 가정하고, n개의 회의가 시작시간이 역순으로 정렬되있다고 가정하면
정렬하는 시간은 O(nlogn)이기 때문에 총 시간 복잡도는 O(nlogn)이다. 



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
#include <iostream> 
#include <algorithm>
 
using namespace std;
 
typedef struct meeting {
    int start;
    int fin;
}meeting;
 
meeting* meeting_arr[100000];
int total_meeting = 0;
int now_num = 0 ;
 
bool cmp_EDGE(meeting* a, meeting* b) { return a->fin < b->fin; }
bool cmp_EDGE_2(meeting* a, meeting* b) { return a->start < b->start; }
 
int main() {
    int total_num = 0;
    cin >> total_num;
 
    for (int i = 0; i < total_num; i++) {
        int start, end;
        cin >> start >> end;
 
        meeting_arr[i] = (meeting*)malloc(sizeof(meeting));
        meeting_arr[i]->start = start;
        meeting_arr[i]->fin = end;
    }
 
    sort(meeting_arr, meeting_arr + total_num, cmp_EDGE);
 
    for (int i = 0; i < total_num; i++) {
        if (now_num <= meeting_arr[i]->start){
 
            int j = i+1; 
            while( (  j < total_num )  &&   ( meeting_arr[i]->fin == meeting_arr[j]->fin )  ){
                j++;
            }
            sort(meeting_arr+i, meeting_arr + j  , cmp_EDGE_2);
 
            now_num = meeting_arr[i]->fin;
            total_meeting++;
        }
    }
 
    cout << total_meeting;
    return 0;
}
cs



Search