[C++, 코딩테스트] Softeer : 강의실 배정 with 그리디 + 우선순위 큐

 

이거는 아이디어가 중요한 것 같다.

 

가장 많은 강의를 배정하기 위해서 가장 먼저 끝나는 수업들을 정렬한다. 이 부분이 우선순위가 강의 종료시간이 된 것이다.

그리고 앞에서부터 하나씩 강의를 배정하고 끝나는 시간과 시작 시간을 확인해서 카운트를 해주면 최대 강의 배정 개수를 구할 수 있다.

 

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

using namespace std;

int main(int argc, char** argv)
{
    int N;
    cin >> N;
    int S, F;
    vector<pair<int, int>> arr;
    for (int i = 0; i < N; i++){
        cin >> S >> F;
        arr.push_back(make_pair(F, S));
    }
    sort(arr.begin(), arr.end());
    pair<int, int> cur = arr[0];
    int count = 1;
    for (int i = 1; i < N; i++){
        int curClassEndTime = cur.first;
        int nextClassStartTime = arr[i].second;
        if (curClassEndTime <= nextClassStartTime){
            count++;
            cur = arr[i];
        }
    }
    cout << count << endl;
    return 0;
}