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

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

 

...알고리즘 같이하는 친구가 준 지혜로 드디어 풀었다..

 

- 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾자
- 회의는 한번 시작하면 중간에 중단 x
- 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있음
- 회의의 시작시간과 끝나는 시간이 같을수도 있다.

 

 

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>

bool cmp(pii a, pii b)
{
    if (a.second == b.second)
    {
        return a.first < b.first;
    }
    return a.second < b.second;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n;
    cin >> n;

    vector<pii> v;

    // 입력
    while (n--)
    {
        int s, e;
        cin >> s >> e;
        v.push_back({s, e});
    }

    // solve - greedy
    int cnt = 0;
    int lastTime = -1;

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

    // 회의를 탐색해본다.
    for (auto &meeting : v)
    {
        int startTime = meeting.first;
        if (lastTime <= startTime)
        {
            cnt++;
            lastTime = meeting.second;
        }
    }

    cout << cnt;
}