회의실 배정 1931 (백준으로 C++ 공부하기 32일차)

문제

1931번: 회의실 배정

 

생각

처음 봤을 때 어떻게 해야 할지 막막했다.

다른 사람의 코드도 읽어 봤는데 이게 어떻게 잘 굴러가는 건지 잘 모르겠어서 그것을 참고만 하고 나의 새로운 코드를 작성했다.

 

먼저 배열을 다 받은 다음에 정렬을 시킨다

전의 끝나는 시간보다 현재의 시작하는 시간이 더 작고

현재의 끝나는 시간이 전의 끝나는 시간보다 작거나 같으면

끝나는 시각을 현재의 끝나는 시각으로 최신화해준다.

 

전의 끝나는 시간보다 현재의 시작하는 시간이 크거나 같으면 회의가 새로 생기는 것이기 때문에

카운트를 하나 늘려준다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;

int main() {
    int n; cin >> n;

    vector<pii> v;
    for(int i = 0; i < n; i++) {
        int a, b; cin >> a >> b;
        v.push_back({a, b});
    }

    sort(v.begin(), v.end());
    int cnt = 1;
    int prevEndTime = v[0].second;
    for(int i = 1; i < n; i++) {
        auto[curStartTime, curEndTime] = v[i];
        if(curStartTime < prevEndTime) {
            if(curEndTime <= prevEndTime) {
                prevEndTime = curEndTime;
            }
        }
        else {
            cnt++;
            prevEndTime = curEndTime;
        }

    }
    cout << cnt;
}