BOJ 1931 - 회의실 배정

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

1931번: 회의실배정

 

Greedy 를 이용해 푸는 문제이다.

 

회의의 시작시간을 기준으로 정렬을 하고,

회의의 끝 시간을 기준으로 정렬을 한다

-> 이렇게 정렬을 두번 하는 이유는

(4,5) , (3,5) , (1,5)

 

같이 끝나는 시간만 동일한 케이스가 있을 경우

현재 상황에서 가장 최선의 선택을 하는 Greedy 의 원칙과 부합하지 않을 수 있기 때문이다

가장 먼저 시작하는

1초 부터 잡아야 Greedy 의 원칙과 맞기 때문에

(1,5) , (3,5) , (4,5) 로 정렬되어야 한다.

 

또한 회의가 끝나는 시간 보다 크거나 같은 경우에만 

다음 회의 시간으로 잡을 수 있다

 

- c++

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
 
using namespace std;
 
int N, minimum, cnt;
vector<pair<int, int>> vec;
 
bool compare(const pair<int, int> &a, const pair<int, int> &b) {
    return a.second < b.second;
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        vec.push_back(make_pair(x, y));
    }
 
    sort(vec.begin(), vec.end());
    sort(vec.begin(), vec.end(), compare);
 
    minimum = vec[0].second;
    cnt++;
 
    for (int i = 1; i < N; i++) {
        if (vec[i].first >= minimum) {
            minimum = vec[i].second;
            cnt++;
        }
    }
 
    cout << cnt;
 
    return 0;
}