[그리디]백준 1931번 회의실 배정(C++)

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

 

그리디 알고리즘을 배운다면

무조건 나오는 문제 중 하나이다.

 

이건 그냥 외우다 시피 해라!~!

 

https://source-sc.tistory.com/59

[탐욕 알고리즘][2] - 회의실 배정 문제

이 블로그에서 회의실 배정 문제에 대해 굉장히 자세히 알려주고 있다!

 

그리디 알고리즘을 사용하는 건 알겠는데 어떻게 사용하냐!

 

끝나는 시간을 기준으로 생각하면 된다

 

예를들어

 

q에 들어가는 회의 시간은

"종료 시간이 가장 빠른" 회의부터 들어가게 된다.

 

 

예를들어 

1 4

5 6

4 6 

이란 회의시간이 있고

 

정렬 된 상태는

1 4

4 6

5 6

이다.

그럼 4이후로 시작하는 회의가 

5 6

4 6

이 있다.

물론 직관적으로 보기에는 6 5 가 회의시간이 더 짧으니 이걸 선택하는 것은 좋지만

 

전체적으로 보자면 선택한 회의의 수는 똑같다

 

왜냐면 끝나는 시간을 기준으로 하는 것이기 때문에

 

그 사이에 빈 시간대에 대한 회의가 있었다면 이미 들어갔기 때문이다.

 

예를들어, 4~5라는 시간표가 있었다면 이미 들어갔을 것이다.

 

 

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <utility>

using namespace std;

int main()

{

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

    int n;

    cin >> n;

    for (int i = 0; i < n; i++)

    {

        int x, y; // 시작과 끝

        cin >> x >> y;

        q.push({y, x});

    }

    int count = 0;

    int e = 0;

    while (!q.empty())

    {

        int a, b;

        b = q.top().first;

        a = q.top().second;

        // cout << a << " " << b << "\n";

        if (e <= a)

        {

           

            count++;

            e = b;

        }

        q.pop();

    }

    cout << count << "\n";

}

 

그래서, 자동으로 끝나는 시간으로 오름차순 정렬을 하는 우선순위 큐를 생성해주었다.