BOJ 1931번 회의실 배정

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

github : https://github.com/junho0956/Algorithm/blob/master/1931/1931/%EC%86%8C%EC%8A%A4.cpp

 

회의실을 최대한 많이 사용하기 위해서는 회의의 시작시간이나 회의시간 이 중요한게 아니고

회의가 언제 끝냐느냐가 가장 중요합니다.

회의가 빨리 끝나는 순으로 정렬하여서 가능한 모든 회의를 진행하면 이게 최대의 횟수가 됩니다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
vector<pair<int, int> > v;
int N, f, s;
 
bool cmp(pair<int, int>& a, pair<int, int>& b) {
    if (a.second != b.second) return a.second < b.second;
    else return a.first < b.first;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> f >> s;
        v.push_back({ f,s });
    }
    
    sort(v.begin(), v.end(), cmp);
 
    int cnt = 1, fin = v[0].second;
    for (int i = 1; i < v.size(); i++) {
        if (v[i].first >= fin) {
            cnt++;
            fin = v[i].second;
        }
    }
 
    cout << cnt;
    return 0;
}