BOJ 1931번 : 회의실배정

그리디 알고리즘을 사용하는 문제였다.

처음에는 무작정 회의 시간이 가장 짧은것 순으로 붙이면 되겠다 라고 생각 했다.

하지만, 순서가 정해져야 하므로 말도 안되는 방법이다.

 

이 문제의 가장 중요한 부분은 "가장 먼저 끝나는 회의"의 순서를 찾아야 한다는 것이다.

먼저 끝나는 회의를 찾고, 끝나는 시간 이후에 가장 먼저 시작하는 회의를 찾는 것을 반복하면 이 문제를 해결할 수 있다.

 

만약 먼저 끝나는 회의의 정렬을 위해 퀵소트를 사용한다면, 워스트 케이스의 경우 O(N^2)의 시간 복잡도를 가지게 되므로 시간이 부족하게 된다. 

 

이때문에 C++ 라이브러리에 있는 sort()를 사용하였다.

 

개인적으로 틀린 부분은 회의의 시작시간과 끝나는 시간이 같은 경우의 예외 사항때문에 많이 틀렸다.

 

(5,8) (8,8) (8,8) 처럼 회의가 주어질 경우 (5,8)회의를 진행 한 후 (8,8)회의를 한개만 선택하여 진행이 가능한 줄 알았는데, 문제의 조건에서 시작과 끝이 같을 경우 시작하자마자 끝난다는 조건에 의해 (8,8) 두개를 모두 선택 할 수 있다.

 

또한, 위의 경우를 위해 회의 끝시간을 기준으로 정렬을 할때 회의 시작하는 시간또한 오름차순으로 정렬해야 한다.

 

이를 위해 sort()사용시 추가적인 함수를 만들어주어야 한다.

 

<소스코드>

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
 
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
    if (a.second == b.second) 
        return a.first < b.first;
 
    return a.second < b.second;
}
 
void Solve(int n, vector<pair<int, int>> v) {
    sort(v.begin(), v.end(), cmp); // sort by second num
 
    int res = 1;
    int tem = v[0].second;
 
    for (int i = 1; i < v.size(); i++) {
        if (v[i].first >= tem) {// 이전 회의 다음에 가장 빨리 시작하는 회의
            res++;
            tem = v[i].second;
        }
    }
    cout << res;
 
}
 
int main() {
 
    int n;
 
    cin >> n;
    vector<pair<int, int>> v;
    int x, y;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        v.push_back(make_pair(x, y));
    }
 
    Solve(n, v);
 
}

<문제>

www.acmicpc.net/problem/1931

1931번: 회의실배정