1931: 회의실 배정

[minsoo0715]

1931: 회의실 배정

소스 코드

아이디어

회의실 배정을 할 때 많은 회의실을 배정할 수 있는 경우는 바로 끝나는 시간이 빠른 경우를 고를 때라고 생각할 수 있다. 또한 끝나는 시간이 동일하면, 더 일찍 시작할수록 유리하다.

따라서 끝나는 시간 기준, 내림차순으로 정렬하고, 끝나는 시간이 동일한 경우 시작 시간 기준으로 내림차순으로 정렬하고, 고르면 된다.

구현

sort()에 comparator 람다 표현식을 넘겨서 정렬 후, 시간이 겹치지 않는다면 그 회의를 카운팅한다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
#define endl '\n';
vector<pair<int, int>> c = vector<pair<int, int>>(100001);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, cnt = 1, end;
    cin >> N;
    for(int i = 0; i<N; ++i) {

        cin >> c[i].first >> c[i].second;
    }

    sort(c.begin(), c.begin()+N, [](auto p1, auto p2) {
        if(p1.second == p2.second) {
            return p1.first < p2.first;
        }
        return p1.second < p2.second;
    });

    end = c[0].second;

    for(int i = 1; i<N; ++i) {
        if(end <= c[i].first) {
            ++cnt;
            end = c[i].second;
        }
    }
    cout << cnt;
    return 0;
}