[C++] BAEKJOON 1931회의실 배정

어느 회의실을 선택할지에 대해서 그리디 알고리즘 을 통해 접근합니다. 현재 순간에 최선의 선택지를 고르는 것으로 말이죠. 그렇다면 현재 순간의 최선이라면 어떤 희의를 골라야할까요?

여러 가지 경우를 생각할 수 있습니다. 시작 시간이 가장 빠른 회의, 회의시간이 가장 짧은 회의 등등 여러 경우가 있지만 각각은 반례가 존재하고 정답은 종료시간이 가장 빠른 회의입니다. 언제 시작하더라도 얼마나 회의를 하더라도 가장 빠르게 종료한다면 다음 회의를 진행하는데 있어서 유리합니다.

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

1931번: 회의실배정

#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;

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

int main(int argc, const char * argv[]) {
    
    pair <int,int> con[100000];
    
    int N;
    cin >> N;
    
    for (int i=0;i<N;i++){
        cin >> con[i].first >> con[i].second;
    }
    
    sort(con, con+N,compare);
    
    int conCount = 1;
    int endTime = con[0].second;
    
    for (int i=1;i<N;i++){
        if (con[i].first >= endTime){
            conCount++;
            endTime = con[i].second;
        }
    }
    
    cout << conCount << "\n";
    return 0;
}