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

1. 문제

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

1931번: 회의실 배정

 

2. 풀이

끝나는 시간이 빠른 회의를 우선적으로 선택함으로써 남은 시간을 최대한 활용할 수 있게 됩니다.

다시 말해, 어떤 회의가 빠르게 끝나면 그 후에 다른 회의들을 더 많이 배정할 수 있습니다.

 

예시)
회의 리스트:
A: 1-4
B: 3-5
C: 0-6
D: 5-7
E: 3-8
F: 5-9
G: 6-10
H: 8-11
I: 8-12
J: 2-13
K: 12-14

1. 끝나는 시간을 기준으로 오름차순 정렬을 합니다:
A: 1-4
B: 3-5
D: 5-7
F: 5-9
G: 6-10
C: 0-6
E: 3-8
H: 8-11
I: 8-12
K: 12-14
J: 2-13

2. 이제 리스트의 맨 앞에서부터 회의를 확인하며 배정합니다:
   - 첫 번째 회의 A: 1-4 를 선택합니다.
   - 다음 회의 B: 3-5 는 A와 겹치므로 건너뜁니다.
   - 그 다음 회의 D: 5-7 는 A와 겹치지 않으므로 선택합니다.
   - 회의 F, G는 D와 겹치므로 건너뜁니다.
   - 회의 C는 A와 겹치므로 건너뜁니다.
   - 회의 E도 A와 겹치므로 건너뜁니다.
   - 회의 H: 8-11은 D와 겹치지 않으므로 선택합니다.
   - I는 H와 겹치므로 건너뜁니다.
   - K: 12-14는 H와 겹치지 않으므로 선택합니다.
   - J는 A와 겹치므로 건너뜁니다.

결국 선택된 회의는 A, D, H, K 총 4개입니다.

이렇게 "끝나는 시간"을 기준으로 오름차순 정렬하여 탐색하는 방식으로 최대 개수의 회의를 선택할 수 있습니다.

 

3. 코드

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

using namespace std;

struct Meeting {
    int start, end;
};

bool compare(const Meeting &a, const Meeting &b) {
    if (a.end == b.end) return a.start < b.start;
    return a.end < b.end;
}

// 1931
/*
    끝나는 시간이 빠른 회의를 우선적으로 선택함으로써 남은 시간을 최대한 활용하는 것이 문제의 핵심
*/
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N, answer = 0, end_time = 0;
    cin >> N;

    vector<Meeting> meetings(N);

    for (int i = 0; i < N; i++)
        cin >> meetings[i].start >> meetings[i].end;

    // 1. 끝나는 시간 기준으로 정렬
    sort(meetings.begin(), meetings.end(), compare);

    // 2. 회의를 탐색하면서 조건에 맞는 회의 선택
    for (int i = 0; i < N; i++) {
        if (meetings[i].start >= end_time) {
            end_time = meetings[i].end;
            answer++;
        }
    }

    cout << answer;

    return 0;
}