[백준 1931] 회의실 배정

[백준 1931] 회의실 배정

문제 출처 : https://www.acmicpc.net/problem/1931

문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

예제 입력

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력

4

• 문제 이해하기

우리에게 주어진 건 단 하나의 회의실이다. 시작시간과 종료시간을 가진 여러 회의를 입력하고, 회의가 서로 겹치지 않게 최대한 많은 수의 회의를 진행할 수 있는 방법을 찾아야 한다.
문제에 주어진 조건이 몇 가지가 있다.1. 회의가 한번 시작하면 중간에 중단되지 않는다는 점2. 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있는 점3. 회의의 시작 시간과 종료 시간이 같을 수다 있다는 점 (이때는, 시작하자마자 끝나는 것으로 간주)
이 조건을 모두 만족하는 최대 회의 진행 가능 수를 출력해주면 되는 문제다.

• 계획 및 문제해결

현재 문제 예제에 나온 입력 결과에 따른 회의 진행을 막대 그림으로 나타내면 아래와 같다.

이 문제도 그리디 알고리즘으로 접근해야 한다. 매 순간마다 최선의 방법을 통해 접근해서 최대한 많은 회의를 진행해야 되기 때문이다. 그렇다면, 최선의 방법을 찾기위해 어떤 규칙을 적용하면 좋을까? 반례가 없는 방법을 찾아야한다.

회의를 일찍 시작하는 순으로 접근하면?!

가장 처음 생각나는 방법이다. 일찍 시작하는 순으로 정렬하면 구할 수 있지 않을까?

하지만 아래 그림과 같은 반례가 존재한다.

일찍 시작했지만, 종료시간이 늦어서 중간에 빨리 끝나는 회의가 있으면 최대 회의 수를 구할 수 없다.

그렇다면 회의가 짧은 순으로 구하면?!

위에서 존재했던 반례를 이용해 짧은 순으로 정렬하면 가능할까 싶지만, 또 반례가 존재한다.

위 그림과 같이 존재한다면, 아무리 짧은 회의라도 최대 회의 수를 구할 수 없게 된다.

일찍 끝나는 회의를 기준으로 잡으면?!

회의가 일찍 끝나는 기준을 잡으면, 회의를 선택할 수 있는 범위가 넓어진다.

일찍 끝나면 더 회의를 많이 진행할 수 있기 때문이다. 이 조건을 이용하면 가능할 것 같다.

빨리 끝나는 조건을 이용했을 때, 빨간색 숫자 표시로 진행하면 최대 회의 수를 구할 수 있게 된다.

또한 파란색 숫자로 표시된 영역으로도 최대 회의 수와 개수가 일치하는 것을 볼 수 있다.

따라서 정렬하는 과정에서 하나로 묶어주자.

코드를 통해서 알아보자.

정렬에 사용할 algorithm과 회의 시간을 저장할 vector를 먼저 선언한다.

그리고 회의 시간을 저장할 구조체를 하나 만든다. (시작시간과 종료시간 두 가지를 저장하기 위해)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct Time {
    int begin; // 회의 시작
    int end; // 회의 끝
};

실제로 값을 입력한 후, algorithm에 존재하는 sort 함수를 통해 정렬을 할 것이다. 이때 위에서 말했던, 최대 회의 수가 여러가지 방식으로 나올 수 있기 때문에, 하나로 묶어주기 위해서 bool형 cmp 함수를 하나 만들어준다.

bool cmp(Time f, Time s) {
    if (f.end == s.end)
        return f.begin < s.begin; // 종료시간이 같다면, 시작시간이 빠른 순
    else
        return f.end < s.end; // 같지 않다면, 종료시간이 빠른순으로 정렬
}

종료시간이 같은 경우에는 시작시간이 빠른 순으로 정렬하고, 같지 않으면 종료시간이 빠른 순으로 정렬해준다.

이를 통해서 위 사진에서 봤던 파란색 숫자의 타일들 대신 빨간색 숫자 타일로 회의 숫자를 먼저 읽어서 적용할 수 있음을 알 수 있다.

이제 main 함수를 통해 총 회의 수 N을 입력받고, for문을 통해 각 회의마다 시작시간과 종료시간을 입력 후 vector를 생성해 구조체 안에 저장시킨다. 그리고 sort 함수로 시작시간, 종료시간을 정렬하며 이때 cmp 함수를 이용한다.

int N;
cin >> N;
 
vector<Time> t(N);
for (int i = 0; i < N; i++) {
   cin >> t[i].begin >> t[i].end;
}
 
sort(t.begin(), t.end(), cmp);

이제 정렬이 완료됐다.

회의 최대수를 저장할 cnt 변수와 회의 종료지점을 저장할 n을 초기화 시켜서 만들고, 모든 회의를 비교하면서 일찍 끝나는 회의 기준으로 조건문을 만들어, 성립할 때마다 cnt를 증가시키면 된다.

int cnt = 0; // 회의 가능한 수
int n = 0; // 회의 종료지점 저장
 
for (int i = 0; i < t.size(); i++) {
    if (n <= t[i].begin) { // 회의 종료 지점이 다음 회의 시작지점보다 작으면
        n = t[i].end; // n에 다음 회의 종료 지점 저장
        cnt++; // 회의 가능수 증가
    }
}

조건문은 회의 종료 시점이 다음 회의 시작지점보다 작거나 같을 때로 기준을 잡으면 된다.

이때마다 n을 해당 회의의 끝지점으로 이동시키면 겹치는 회의는 카운트가 되지 않는 것을 알 수 있다.

이때마다 cnt 수를 증가시키면, for문이 모두 다 돌았을 때 한 회의실에서 최대로 진행할 수 있는 회의 수를 알아낼 수 있게 된다.

• 전체 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct Time {
    int begin; // 회의 시작
    int end; // 회의 끝
};
 
bool cmp(Time f, Time s) {
    if (f.end == s.end)
        return f.begin < s.begin; // 종료시간이 같다면, 시작시간이 빠른 순
    else
        return f.end < s.end; // 같지 않다면, 종료시간이 빠른순으로 정렬
}
 
int main() {
    int N;
    cin >> N;
 
    vector<Time> t(N);
    for (int i = 0; i < N; i++) {
        cin >> t[i].begin >> t[i].end;
    }
 
    sort(t.begin(), t.end(), cmp); // 정렬
 
    int cnt = 0; // 회의 가능한 수
    int n = 0; // 회의 종료지점 저장
 
    for (int i = 0; i < t.size(); i++) {
        if (n <= t[i].begin) { // 회의 종료 지점이 다음 회의 시작지점보다 작으면
            n = t[i].end; // n에 다음 회의 종료 지점 저장
            cnt++; // 회의 가능수 증가
        }
    }
 
    cout << cnt << endl;
}