1931: 회의실 배정 - 그리디

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

 

문제요약

한 개의 회의실, 겹치지 않게 최대한 많은 회의를 진행하려면?

 

난이도

Silver 1

---

풀이 포인트

• 그리디
  • 가장 첫번째 회의는 진행한다고 가정하고 그 다음에 열 수 있는 회의부터 고려

---

REVIEW

 

우선 문제를 제대로 안 읽어서 해당 회의를 모두 진행할 수 있는 최소 회의실 수를 구하는 줄 알고,

범위를 봤는데 2^32-1? 포기해버렸다.

 

아직 pair, map, set 등 자료 구조를 적절히 자유자재로 구사할 줄 모르는 것 같다.

요런 아이큐 테스트 스러운 문제는 꼭 맞추고 싶은데 또 답으로 달려갔기에 반성.

 

---

CODE

#include <bits/stdc++.h>
using namespace std;

int from, to, n, idx = 0, ret =1;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>> n;

    vector<pair<int, int>> v;

    for(int i = 0; i < n; i++){
        cin >> from >> to;
        v.push_back({to, from});
    }

    sort(v.begin(), v.end());

    from = v[0].second; // 1
    to = v[0].first; //4

    for(int i = 1; i < n; i++){
        //3 < 4
        // 0 < 4
    
        if(v[i].second < to) continue;

        // 5 > 4
        from = v[i].second; //7
        to = v[i].first;    //5
        ret++; 
    }

    cout << ret << '\n';
    return 0;
}