[C++] 백준 2931 : 회의실 배정

문제

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

 

 

풀이

1. 회의실 정보를 정렬 : end 기준 오름차순 정렬 + 동일 end에 대해 start 기준 오름차순

2. 마지막으로 선택된 종료시간을 기억하면서, 해당 종료시간 뒤에 현재 확인한 회의 end 값 갱신

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct State{
    long long start, end;
};

int n;
vector<State> v;

// end 기준 오름차순, 같으면 start 오름차순
bool cmp(const State& a, const State& b) {
    if (a.end == b.end) return a.start < b.start;
    return a.end < b.end;
}

int main()
{
    cin >> n;
    for(int i=0; i<n; i++){
        long long s, e;
        cin >> s >> e;
        v.push_back({s,e});
    }
    
    // end 기준 오름차순 정렬
    sort(v.begin(), v.end(), cmp);
    
    int ans = 0;
    long long last_end = 0;
    
    for(State cur : v){
        if(cur.start >= last_end){
            ans++;
            last_end = cur.end;
        }
    }
    
    cout << ans << "\n";
    return 0;
}

 

 

---

메모

start 기준 오름차순 정렬인지, end 기준 오름차순 정렬인지 햇갈렸던 문제였다~ ㅜ 

그리고 cmp 함수 작성하는 것 더 공부하기