[백준] 1931번 회의실 배정

문제 내용

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

1931번: 회의실 배정

 

해결 코드

 

#include <algorithm> //sort를 사용하기 위한 header 파일
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
 
    int n;
    int ans = 0;
    vector<pair<int, int>> v;
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int s, e;
        cin >> s >> e;
        v.push_back(make_pair(e, s)); //종료 시간을 기준으로 하기 위함
    }
 
    sort(v.begin(), v.end());
 
    int i = 0;
 
    while (i < n) {
        int end = v[i].first;
        ans++;
        i++; //본인 확인을 제외하기 위해 넣음
 
        while (v[i].second < end && i < n) { 
            i++;
        }
    }
 
    cout << ans;
}
 

 

주요 개념 

그리디 알고리즘(Greedy Algorithm):  활동선택 

 

주의 사항

1. 시작시간과 종료시간이 같을수 있다는 조건에 유의해야함
2. 시간 복잡도를 O(n)으로 해야 시간 초과가 나지 않음

 

참고한 곳

https://doorbw.tistory.com/75

알고리즘 #10_ 그리디 알고리즘(Greedy algorithm): 활동 선택 문제