[ 백준 ] 1931 / 회의실 배정

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
79/228
post-thumbnail
post-custom-banner

# Appreciation

/*
 * Problem :: 1931 / 회의실 배정
 *
 * Kind :: Greedy
 *
 * Insight
 * - Greedy 의 가장 대표적인 문제
 *   + 빨리 시작하는 순서대로 회의를 배정할까?
 *     # |-----------------------|
 *        |-| |-| |-| |-| |-| |-|
 *   + 시간이 적게 걸리는 회의 순서대로 회의를 배정할까?
 *     #    |--|
 *       |---||---|
 *   + 빨리 끝나는 순서대로 회의를 배정할까?
 *     # ...아무리 생각해도 반례가 없다
 *       -> 빨리 끝나는 순서대로 회의를 배정했을 때
 *          배정된 회의의 순서를 a0, a1, ..., an 이라고 하자
 *          이 순서에서 몇몇 부분을 조금 늦게 끝난 회의로 배정했을 때
 *          배정된 회의의 순서를 b0, b1, ..., bm 이라고 하자
 *          => 잘 생각해보면 n>=m 일 수밖에 없다
 *             조금 늦게 끝난 회의를 배정했을 경우
 *             빨리 끝난 순서대로 배정했을 때보다 회의를 적게 할 수 있기 때문이다
 *          =>  |---|   <= 빨리 끝난 순서
 *                 |--| <= 조금 늦게 끝난 순서도 포함
 *             |------| / 가능한 해
 *
 *              |---||---| <= 빨리 끝난 순서
 *                 |--|    <= 조금 늦게 끝난 순서도 포함
 *              |---||---| / 가능한 해
 *
 * Point
 * - 시작시간과 종료시간이 같은 회의도 있다
 *   때문에, 정렬할 때 종료시간 기준 빠른 순 뿐만 아니라
 *   시작시간 기준 빠른 순으로 정렬해야 한다
 *   + 3 3 => 1 3
 *     1 3    3 3
 *     3 4    3 4
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

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

using namespace std;

#define endl '\n'

// Set up : Global Variables
struct Meeting { int s, e; };

// Set up : Functions Declaration
bool operator < (Meeting u, Meeting v);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    vector<Meeting> M(N);
    for (int i=0; i<N; i++)
        cin >> M[i].s >> M[i].e;

    // Process
    sort(M.begin(), M.end());
    int ans = 0 /* 지금까지 한 회의의 수 */, et = -1 /* 마지막 회의 종료시간 */;
    for (int i=0; i<N; i++) {
        /* 현재 회의 M[i] 의 시작시간이 마지막 회의 종료시간보다 같거나 빠르면 */
        if (et <= M[i].s) {
            ans++; /* 회의 시작 */
            et = M[i].e; /* 마지막 회의 종료시간 갱신 */
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
bool operator < (Meeting u, Meeting v)
/* Meeting 구조체 정렬을 위한 함수 */
{
    /* 종료시간이 빠른 순, 시작시간이 빠른 순으로 정렬 */
    return make_pair(u.e, u.s) < make_pair(v.e, v.s);
}
profile
이런 미친 게임을 봤나! - 옥냥이
post-custom-banner

0개의 댓글