티스토리 뷰

알고리즘/BOJ

BOJ 1931, 회의실 배정

아테즈 2019. 3. 25. 20:25

문제

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

입력

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


이 문제도 탐욕법으로 풀 수 있습니다.


회의가 가장 빨리 끝나는 순서대로 정렬한 후, 끝나는 시간이 같으면


시작 시간이 빠른 순서대로 골라주면 최대한 많이 넣을 수 있습니다.


최적 부분 구조를 증명해 보겠습니다.


우리가 고른 정답의 집합을 S라고 하고, S안에는 가장 빨리 끝나는 회의가 들어있지


않다고 해봅시다.


S= {s1, s2, s3, ... }


우리가 고른 S의 원소들을 정렬한 다음, 가장 앞의 원소(끝나는 시간이 가장 빠른 회의)를


우리가 처음에 들어있지 않다고 가정한 s1'으로 치환해봅시다.


치환을 하게 되면, 정답으로 고른 집합은 S = {s1', s2, s3, ... } 이 되고


그림으로 그려봐도 우리가 구한 정답(최대 가능 회의 개수)에 영향을 미치지 않고 


더 최선의 선택을 할 수 있다는 것을 증명할 수 있습니다.


따라서, 


회의가 가장 빨리 끝나는 순서대로 정렬한 후, 끝나는 시간이 같으면


시작 시간이 빠른 순서대로 골라주면 최대한 많이 넣을 수 있습니다.


정렬하는데 걸리는 시간 O(nlogn) 회의를 고르는데 걸리는 시간 O(n)으로


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
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
 
typedef struct _TIME{
    int st;
    int fin;
} TIME;
 
bool cmp(TIME a, TIME b) {
    if (a.fin < b.fin) {
        return true;
    }
    else if (a.fin == b.fin) {
        return (a.st < b.st);
    }
    return false;
}
 
int main() {
    vector<TIME> v;
 
    int n;
    cin >> n;
    TIME tmp;
    for (int i = 0; i < n; i++) {
        scanf("%d %d"&tmp.st, &tmp.fin);
        v.push_back(tmp);
    }
    int ans = 0;
    sort(v.begin(), v.end(), cmp);
    int last = 0;
    for (auto i = v.begin(); i != v.end(); i++) {
        if ((*i).st >= last) {
            ans++;
            last = (*i).fin;
        }
    }
    cout << ans;
 
    return 0;
}
cs




'알고리즘 > BOJ' 카테고리의 다른 글

BOJ 1049, 기타줄  (0) 2019.03.25
BOJ 1541, 잃어버린 괄호  (0) 2019.03.25
BOJ 1931, 회의실 배정  (0) 2019.03.25
BOJ 11399, ATM  (0) 2019.03.25
BOJ 7576, 토마토  (0) 2018.10.22
BOJ 14731번, 謎紛芥索紀 (Large) - (미분개색기)  (0) 2018.10.20
댓글
댓글쓰기 폼
공지사항
Total
21,753
Today
15
Yesterday
12
링크
TAG
more
«   2022/08   »
  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      
글 보관함