[BOJ_1931_RN] 회의실 배정 Problem Solving

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

문제 해결에 필요한 알고리즘 : 그리디 알고리즘

해설

회의의 정보를 받아 정렬한다. 정렬 기준은 회의가 끝나는 시간이 빠른 순으로 정렬한다.

그 이후 선택가능한 회의 중 가장 빨리 끝나는 회의를 고르면 된다. 회의 정보를 순회하면서 다음 회의 진행이 가능하다면 ( 이전회의시간과 겹치지 않는다면 ) 그 회의를 고르고 카운트를 세어준다. 끝나는 시간이 빠른 순으로 정렬되어있기 때문에 선택가능한 회의 중 가장 빨리 끝나는 회의를 고를 수 있다. 이렇게 모든 회의를 고르고 그 카운트를 세면 최대 사용할 수 있는 회의의 수를 알 수 있다.

 

 

정당성 증명

선택가능한 회의 중 가장 빨리 끝나는 회의를 골랐을 때 이득인 이유는 귀류법으로 증명이 가능하다.

 

S(a, b)를 a보다 같거나 늦게 시작하여 b보다 같거나 일찍 끝나는 회의의 집합이라고 정의한다.

MAX(S) 는 회의실을 사용하는 회의시간표 중 이용할 수 있는 최대 수의 회의라고 정의한다.

 

S(a, c), S(b, c) 가 있고 a > b 라고 했을 때 S(a, c)의 원소는 S(b, c)의 원소가 된다.

그래서 MAX(S(b, c)) >= MAX(S(a, c))가 성립하게 된다.

S(b, c)가 아닌 S(a, c) 가 되는 선택을 하게 된다면 손해를 볼 수 있는 상황이 생긴다.

 

따라서 선택가능한 회의 중 가장 빨리 끝나는 회의를 골랐을 때 최적 선택이 가능하다.

시간복잡도

N : 회의 정보의 갯수

이 코드의 시간복잡도는 정렬 + 회의정보 순회 이다. 정렬을 하는데  만큼 반복되고 순회하는데는  만큼 반복된다. 따라서 시간복잡도는  즉 이 된다.

회의실 배정 코드 [ C++ ]

#include <algorithm>
#include <cstdio>
#include <vector>
struct node {
    int l, r;
};
std::vector < node > v;
int main() {
    int n, cnt = 0, fin = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int l, r;
        scanf("%d%d", &l, &r);
        v.push_back( { l, r } );
    }
    std::sort(v.begin(), v.end(), [](node i, node j) {
        return i.r == j.r ? i.l < j.l : i.r < j.r;
    });
    for (int i = 0; i < n; ++i) {
        if (fin <= v[i].l) {
            ++cnt;
            fin = v[i].r;
        }
    }
    printf("%d", cnt);
    return 0;
}