[백준 1931] 회의실배정

0. 제목

• 백준 1931 회의실배정
• BOJ 1931 회의실배정
• C++ 1931 회의실배정

---

1. 문제

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

---

2. 풀이

• 최대 회의수를 구해야하기 때문에 시작시간을 기준으로 잡으면 안되고 종료시간을 기준으로 잡아야 한다.
• 시작시간을 기준으로 잡아버리면 (1, 10)이 있다고 할 때 (3, 5), (6, 8)이 들어갈 수 없기 때문에 최대수를 구할 수 없다.
• 따라서 종료시간으로 오름차순 정렬을 한 후, 만약 종료시간이 같다면 시작시간 기준으로 오름차순 정렬을 해준다.
• 현재 종료시간보다 나중에 있는 시작시간이 있다면 회의수인 cnt를 1증가시키고 현재 종료시간을 나중에 있는 종료시간으로 갱신해준다.
• 반복문의 모든 loop를 끝낸 이후의 cnt가 최대 회의수이다.

---

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> P;
vector<P> arr;
 
bool comp(P a, P b){
    if(a.second == b.second){
        return a.first < b.first;
    }
    else{
        return a.second < b.second;
    }
}
 
int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    
    int l, r;//left:시작시간, right:종료시간
    for(int i = 0; i < N; i++){
        cin >> l >> r;
        arr.push_back(make_pair(l, r));
    }
    sort(arr.begin(), arr.end(), comp);
    
    int now = arr[0].second;
    int cnt = 1;
    for(int i = 1; i < N; i++){
        if(now <= arr[i].first){
            cnt++;
            now = arr[i].second;
        }
    }
    
    cout << cnt << '\n';
    
    return 0;
}