[PS 백준 - 3.11] 1931번: 회의실 배정

문제 정보

백준 1931번 - 바로가기

• 난이도: 실버 2
• 알고리즘: 그리디 알고리즘

---

코멘트

이 문제는 삽질을 너무 많이 했다. 처음에 생각한 아이디어는 끝나는 시각이 제일 짧은 것을 찾고, 그 시각이 처음 시각과 같아질 때까지 index를 증가시키는 것이였다. 근데 문제는 이걸 너무 복잡하게 풀어서 결국 내 풀이를 포기했다.
도저히 방법을 못 찾겠어서 블로그를 찾아봤는데 방법을 알고 나니깐 정말 허무했다.

int end = 0;
        for (int i = 0; i < n; i++) {
        if (end <= vec[i].first) {
            cnt++;
            end = vec[i].second; // end 개정
        }
    }

동일한 아이디어인데 이렇게 간단한 코드가 있었다니 ㅠㅠ 생각을 조금 더 단순히 할 필요가 있을 것 같다.

---

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;

    vector<pair<int, int>> vec;

    int cnt = 0;

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;

        vec.emplace_back(pair<int, int>(a, b));
    }
    sort(vec.begin(), vec.end(), compare);

    int end = 0;
    
    for (int i = 0; i < n; i++) {
        if (end <= vec[i].first) {
            cnt++;
            end = vec[i].second; // end 개정
        }
    }
    cout << cnt;

    
}