[BOJ] 1931번 회의실배정 풀이(C++)

2017.10.16에 쓰여진 글 입니다.

---

 

문제링크

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

1931번: 회의실배정

 

풀이방법

갓갓 stl 소팅을 이용해주면 되는데 이때 조건을 주는 소팅을 한다.

두가지가 같을때 처리해주는로직만 넣어주면 만사 OK

자세한건 코드에 있는 주석을 참고!

 

소스코드

#include <iostream>
#include <vector>        //vector 위한 헤더
#include <algorithm>    //sort 위한 헤더
#include <utility>        //pair 위한 헤더
 
using namespace std;
 
vector <pair<int, int> > v;        //회의실 사용,끝나는 시간 저장하는 벡터
 
int cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    if (a.second == b.second)
        return a.first < b.first;        //14 24가 있으면 24를 앞에놓겟다    같이끝나지만 24가 더 회의시간이 짧기때문
    return a.second < b.second;            //끝나는시간이 같은게 아니면 끝나는시간이 더 빠른순으로 저장한다
}
int main()
{
    int n;
    int Answer = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int start, end;
        cin >> start >> end;
        v.push_back(make_pair(start, end));        //시작시간 끝나는시간저장
    }
    sort(v.begin(), v.end(), cmp);        //끝나는시간을 기준으로 정렬. 만약 끝나는시간이같다면 시작시간이 늦는 거부터 먼저정렬
                                        //시작시간이 늦는거부터해야 회의시간이 최소가 되기때문에 더 많은 회의를 할수 있음.
    int end = -1;        //초기값으로 끝나는시간 -1넣어줌
    for (int i = 0; i < n; i++)
        if (v[i].first >= end) {        //다음 회의 시작시간이 이전회의 끝나는시간보다 뒤에있으면 
            Answer++;    //회의수 1증가
            end = v[i].second;        //끝나는시간에 그다음회의시간끝나는시간을 넣어준다
        }
    cout << Answer << endl;
 
    return 0;
}