[백준/C++] 1931번 회의실 배정

문제 링크

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

풀이

• 브루트 포스로 풀면 시간 복잡도는 O(2ⁿ) 로 시간초과
• 그리디 알고리즘(최적해)의 시간 복잡도는 O(n log n)
• 끝나는 시간이 빠른 회의부터 선택하면 최대의 회의 개수를 정할 수 있음
  • 회의가 끝나야 다음 회의를 할 수 있음
  • 회의 시간이 빠르게 끝나면 다음 회의를 더 빨리 할 수 있음

코드

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

using namespace std;


int main(){
    // N(1 ≤ N ≤ 100,000)
    int N;
    cin >> N;

    int start,end;
    vector<pair<int, int>> arr;
    while(N--){
        cin >> start >> end;
        arr.push_back({end, start});
    }
    // 끝나는 시간 기준으로 오름차순으로 정렬하여
    // 빨리 끝나는 회의들을 먼저 카운트 할 수 있게 함
    sort(arr.begin(), arr.end());

    int cnt = 0;
    int end_time = 0;

    for(auto times :arr){
        // 끝나는 시간과 시작 시간을 비교하여 회의 개수 카운트
        if(times.second >= end_time){
            cnt++;
            end_time = times.first;
        }
    }
    cout << cnt ;

}