[BOJ] 1931 회의실 배정

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

1931번: 회의실 배정

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

그리디 + 정렬

 

---------------------------------------------------풀이----------------------------------------------------

 

회의 종료 시간을 기준으로 오름차순으로 정렬한다.

정렬된 회의들을 비교하며 총 회의 수를 구한다.

현재 회의 종료 시간을 end1라고 하면, 다음 회의 시작 시간이 end 1이상일 경우 그 회의를 시작할 수 있다.

따라서 end1를 다음 회의의 종료 시간 end2으로 업데이트 하고 회의 수를 나타내는 answer를 1 증가시킨다.

회의 종료 시간이 같을 경우, 회의 시작 시간을 기준으로 오름차순 정렬한다. 회의의 시작 시간과 종료 시간이 같을 수 있기 때문이다!!

예를 들어, [3, 5] [5, 5]가 있을 때,

회의 시작 시간과 상관 없이 정렬하면 [5, 5] [3, 5]와 같이 정렬될 수 있다.

그럼 맨 처음 end는 5가 되고, [3, 5]의 시작 시간인 3이 5보다 작아서 answer=1이 된다.

[3, 5] [5, 5]로 정렬될 경우, 맨 처음 end는 마찬가지로 5지만, [5, 5]의 시작 시간이 end 이상이므로 answer=2가 된다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

vector<pair<int,int> > meeting;

bool cmp(pair<int,int> a, pair<int,int> b){
    // 회의 종료 시간이 같으면 회의 시작 시간을 기준으로 정렬.
    if(a.second == b.second){
        return a.first < b.first;
    }
    return a.second < b.second;
}

int main(void){
    FASTIO;
    int N;
    cin >> N;
    pair<int,int> cur;
    for(int i = 0; i < N; i++){
        cin >> cur.first >> cur.second;
        meeting.push_back(cur);
    }
    // 회의 종료 시간 기준 정렬. 
    sort(meeting.begin(), meeting.end(), cmp);

    int answer = 1;
    int end = meeting[0].second;
    for(int i = 1; i < meeting.size(); i++){
        if(meeting[i].first >= end){
            end = meeting[i].second;
            answer++;
        }
    }

    cout << answer << "\n";

    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

그리디는 처음부터 제대로 찾았는데, 회의 시작 시간을 정렬하지 않아 85%에서 틀렸었다.

문제에 나온 "회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다." 라는 문구를 잘못 이해해서 구현했기 때문이다.

[3, 3]과 같이 한 회의의 시작시간과 끝나는 시간이 같을 수도 있다는 의미인데, 

[2, 4] [4, 5]와 같이 회의가 연속해서 이루어질 수 있다는 의미로 받아들였다.ㅠㅠ