BOJ 1931 회의실 배정 / C++

문제 링크 : https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

문제 풀이

코드를 보면서 이해하는 편이 빠르다.

회의의 시작 시간과 끝나는 시간을 pair로 저장하는 vector를 만든다.

최대 배정 가능 회의를 넣는 벡터도 생성해준다.

 

회의들을 모두 입력받은 뒤, 가장 빨리 끝나는 작업 순으로(즉, pair의 second) 정렬을 해주기 위해

compare 함수를 만든다. 이 때, a.second와 b.second가 같다면 first도 똑같이 비교해줘야 한다.

예를 들어, 6개의 회의가

1 3

3 100

4 5

6 6

5 6

7 7 의 순서로 입력되었다면

정렬될 때 1 3 -> 4 5 -> 6 6 -> 5 6이 아니라 1 3 -> 4 5 -> 5 6 -> 6 6의 순서로 정렬되어야 한다.

앞선 경우와 같이 정렬되면 가능한 회의가 하나 줄어들게 된다.

 

새로 알게 된 사실로 compare 함수에서 비교값이 같을 때 true를 리턴하면 런타임 에러 SegFault가 뜨기 때문에

false 또는 다른 비교값을 리턴해야한다.

 

정렬된 후 첫 번째 회의를 available에 넣고 minVal에 첫 번째 회의 종료 시간을 넣는다.

이 minVal에는 현재 진행중인 회의가 끝나는 시간이 들어간다.

for문을 1부터 돌며 해당 인덱스의 회의가 진행될 수 있는지 판단한다.

판단 기준은 현재 회의 종료 시간과 다음 회의 시작시간을 비교한다. 회의를 진행할 수 있다면

minVal을 해당 회의의 종료시간으로 업데이트 해준다.

 

for문이 끝났을 때, available 벡터의 크기가 가능한 회의의 최대 개수이다.

 

소스 코드

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

bool comp(pair<long, long> a, pair<long, long> b){
    if(a.second < b.second) return true;
    else if(a.second == b.second){
        return a.first < b.first;
    }
    else {
        return false;
    }
}

int main(){
    vector<pair<long long, long long> > cons; //conferences
    vector<pair<long long, long long> > available;
    int n;
    cin >> n;

    for(int i=0; i<n; i++){
        long long st, en;
        cin >> st >> en;
        cons.push_back(make_pair(st, en));
    }

    sort(cons.begin(), cons.end(), comp); //작업이 빨리 끝나는 순으로 정렬

    available.push_back(make_pair(cons[0].first, cons[0].second));
    long long minVal = cons[0].second;

    for(int i=1; i<n; i++){
        if(cons[i].first >= minVal){
            available.push_back(make_pair(cons[i].first, cons[i].second));
            minVal = cons[i].second;
        }
    }

    cout << available.size();
}