[C++] BaekJoon 1931 회의실 배정

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

---

이 문제는 회의실을 최대한 활용하여 겹치지 않는 회의를 많이 배정하는 것을 목표로 한다.

이런 유형의 문제는 그리디 알고리즘을 활용하여 효율적으로 해결이 가능하다. 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> list;

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

    int time = list[0].first;
    int count = 1;
    for (int i = 1; i < n; i++)
    {
        if (list[i].second >= time)
        {
            count++;
            time = list[i].first;
        }
    }
    cout << count;
}

설명

회의가 시작 하는 시간과 끝나는 시간을 저장하기 위해 vector를 pair를 사용하여 쌍으로 저장한다.

끝나는 시간을 기준으로 오름차순 정렬하기 위해 vector의 first에 end, second에 start를 저장하여

sort를 사용하여 오름차순으로 정렬한다. 

 

현재 시간을 변수로 설정하고 가장 빨리 시작하는 회의의 끝나는 시간을 현재 시간으로 설정하고, 

count 변수에 1를 설정한다. 

 

현재 시간보다 다음 회의 시작 시간이 크거나 같을 때, 카운트를 증가시키고 현재 시간을 다음 회의의 끝나는 시간으로

업데이트한다.