[백준] 1931 회의실 배정 c++

 

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

KEY

• 대표적인 그리디 유형의 문제로, 구현이 어렵지는 않았다.
• 회의가 일찍 끝나는 순으로 정렬하고, 만약 끝나는 시간이 같은 경우 먼저 시작하는 순으로 정렬해야 한다.
•  sort함수의 boolean 인자를 새롭게 만들어서 sort함수를 재정의했다. 

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int N;
int answer;
vector<pair<int, int>> v;
 
bool compare(pair<int, int> p1, pair<int, int> p2) {
    if (p1.second == p2.second) 
        return p1.first < p2.first;
    return p1.second < p2.second;
}
 
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int start, end;
        cin >> start >> end;
        v.push_back({ start,end });
    }
 
    //일찍 끝나는 순 정렬 (끝나는 시간이 같다면 일찍 시작하는 순 정렬)
    sort(v.begin(), v.end(), compare);
 
    int t = v[0].second;
    for (int i = 1; i < v.size(); i++) {
        if (v[i].first >= t) {
            t = v[i].second;
            answer++;
        }
    }
    cout << answer+1; //맨 첫번째 회의 포함
}