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

문제

 

---

풀이

 

개인적인 비하인드 때문에 나혼자 140만원 문제라고 부르는 회의실 배정 문제이다.

 

이 문제에서 중요한 것은 시작하는 시각일까 끝나는 시각일까?

당연히 끝나는 시각이다. 0시에 시작해서 12시에 끝나는 것보다야 3시에 시작해서 4시에 끝나는게 회의실을 좀 더 효율적으로 사용할 수 있는 방법일 것이다.

 

그렇다면 끝나는 시각이 작은 순서로 정렬한다고 치고 같은 때에 끝나는 회의가 2개 이상 있다면 어떤 회의를 우선으로 해야할까?

끝나는 시각이 같고, 시작하는 시각이 다른 다음과 같은 회의 A, B가 있다.

회의 A를 먼저 투입했을땐, 회의 A가 끝난 뒤 회의 B를 진행할 수 있다.

회의 B를 먼저 투입했을땐, 회의 B가 끝난 뒤에 회의 A를 진행할 수 없다. 이미 4시인데 2시부터 해야했을 회의 A를 할 순 없다.

 

이렇게 정렬만 하면 나머지는 어렵지 않다.

---

소스코드

 

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

struct meeting {
    int start_time, end_time;
};
meeting* m = new meeting[100001];

bool cmp(const meeting& m1, const meeting& m2) {
    if (m1.end_time < m2.end_time) //빨리 끝나는게 앞으로
        return true;
    else if (m1.end_time == m2.end_time) //끝나는 시간 같다면 먼저 시작하는걸 앞에
        return m1.start_time < m2.start_time;
    else
        return false;
}

int meetings(int N) {
    int end_time = 0, cnt = 0;

    for (int i = 0; i < N; i++) {
        if (m[i].start_time >= end_time) { //이전 회의가 끝난 뒤 시작하는 거라면
            end_time = m[i].end_time; //끝나는 시간 초기화
            cnt++; //가능 회의 증가
        }
    }
    return cnt;
}

int main() {
    int N, last_time = 0;

    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> m[i].start_time >> m[i].end_time;
    sort(m, m + N, cmp); //정렬
    cout << meetings(N);
}

지금 몇시가 됐는지 알아야 새로운 회의의 시작 시각과 비교해 회의실을 배정하기 때문에 meetings 함수에 ent_time 변수를 둔다.