[C++] 백준 1931: 회의실 배정

문제 이해

- 1개의 회의실에 N개의 회의를 배정할 계획이다.

- 시작 시간과 끝나는 시간이 주어진다.

- 회의 사용표를 만들 때, 겹치지 않으며 할 수 있는 회의의 개수의 최댓값을 구하라

- 회의의 경우 끝나는 것과 동시에 다음 회의가 시작할 수 있다.

- 또한, 회의의 시작 시간과 끝나는 시간이 같을 수도 있다.

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 128MB

 

<입력>

- N: 회의의 수 (1 ~ 100,000, 10^5)

- N개의 줄에 걸쳐 각 회의의 시작 시간, 끝나는 시간 (0 ~ 2^31-1)

 

<출력>

- 사용할 수 있는 회의의 최대 개수를 구하라.

 

 

---

문제 풀이

회의를 최대한 많이 사용해야 하므로

그리디 알고리즘과 정렬을 사용해야겠다고 생각했다.

 

 

그렇다면 중요한 건 정렬을 '무엇'을 기준으로 '오름차순 혹은 내림차순' 할 것이냐는 것이다.

경우의 수는 총 4가지가 있는데,

1. 시작 시간을 기준으로 오름차순 정렬

2. 종료 시간을 기준으로 오름차순 정렬

3. 시작 시간을 기준으로 내림차순 정렬

4. 종료 시간을 기준으로 내림차순 정렬

 

내림차순 정렬의 경우 의아할 수 있으나 역순으로 탐색하는 방법도 있기에 경우의 수로 고려하였다.

 

자 그럼 각 경우의 수를 하나하나 생각해보자

1번의 경우 시작 시간이 빠른 걸 택할 수 있을 것이다.

 

하지만, 

0 14의 경우와 같이

종료 시간이 엄청 클 경우 최댓값을 구할 수 없으므로 기각했다.

 

 

2번의 경우 종료 시간이 빠른 걸 택할 수 있다.

종료 시간이 빠른 순서로 택할경우 시작 시간이 아무리 빨라도 그 경우가 최적일 것이다.

0 5

0 6

1 6

과 같이 회의가 3개 있을 때, 시간표에 제일 효율적인 것은 당연히 0 5의 경우일 것이다.

 

종료 시간이 빠른 순으로 택한 후에

시작 시간이 종료 시간 이상인 것을 택해줄 경우 최댓값을 구할 수 있다.

 

이때 stl 라이브러리의 sort 함수의 경우 첫 번째 원소를 기준으로 오름차순 정렬하므로

첫 번째 원소에 종료 시간을 넣어주었다.

for(int i = 0; i < n; i++){
    int start, end;
    cin>>start>>end;
    v.push_back({end, start});
}

sort(v.begin(), v.end());

 

 

이미 답을 구하는 경우의 수는 파악했지만 3, 4번도 고려해보자.

 

3번의 경우

역순으로 넣는다고 해도 1번과 같이 종료 시간때문에 최적으로 시간표에 넣을 수 없을 것이다.

 

 

4번의 경우, 

역순으로 넣으면 분명 끝부터 채워넣을 수 있으니 효율적으로 보일 수 있다.

하지만 1번의 반례(0 14)와 같이

시작 시간이 엄청나게 빠를경우 효율적이지 않으므로 기각되었다.

 

 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define INF 987654321

vector <pair<int, int>> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin>>n;
    for(int i = 0; i < n; i++){
        int start, end;
        cin>>start>>end;
        v.push_back({end, start});
    }
    
    sort(v.begin(), v.end());

    int end = v[0].first;
    int ans = 1;

    int size = v.size();
    for(int i = 1; i < size; i++){
        if(v[i].second >= end){
            ans++;
            end = v[i].first;
        }
    }

    cout<<ans;
    return 0;
}

 

 

 

---

배운 점

단순한 정렬 문제라고 해도 각 경우의 수에 대하여 잘 따져봐야 된다는 걸 배웠다.

포스트에는 빠르게 답을 찾은 것처럼 적었지만 사실 꽤나 곤혹을 치뤘다...