[1931] 회의실배정

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

1931번: 회의실배정

 

---

 

그리디 알고리즘을 사용하는 문제....

dp문제를 많이 풀다가 그리디 알고리즘 문제를 풀려고 하니 자꾸 dp식으로 접근하는 바람에 시간초과가 계속 났었다. 

 

그리디 알고리즘이란, 현재 상태에서 가장 최선의 선택인 것만 골라서 진행하는 알고리즘이다.

즉 다른건 아무것도 생각하지말고 그냥 현재 상태에만 집중하면 되는 것이다.

 

---

 

🔎 해결방법 

1. 회의 시작 시간을 기준으로 오름차순 정렬, 시작 시간이 같다면 끝나는 시간이 빠른 것부터 정렬(sort 함수 사용)

2. tmp을 회의가 가장 늦게 시작하는 시간으로 초기화

3. for문을 돌면서 현재 회의 시작 시간보다 이전 회의가 끝나는 시간이 더 이르거나 같은 경우, 이 두가지 회의를 모두 선택할 수 있으므로 cnt를 1 증가시켜준다. (cnt는 0이 아니라 1로 초기화 되어있어야 함)

4. tmp를 현재 회의 시작 시간으로 업데이트 해줌

 

 

이렇게 입력받은 회의 정보를

 

 

 

 

 

 

이렇게 정렬해주고 맨 끝에서부터 비교를 시작하면 됨!

 

 

 

 

 

 

---

 

💡 내 코드(C++)

// [1931] 회의실배정
// https://www.acmicpc.net/problem/1931
// 그리디 알고리즘

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

int main(void)
{
    int n, cnt = 1; // 회의의 수, 사용할 수 있는 회의 수
    vector<pair<int, int> > meet; // 회의의 정보
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        int start, end; // 회의 시작 시간, 끝나는 시간
        scanf("%d %d", &start, &end);
        meet.push_back(make_pair(start, end));
    }

    sort(meet.begin(), meet.end()); // 회의 시작 시간 기준으로 오름차순 정렬
    /*vector<pair<int, int>> v 꼴인 경우 sort는 디폴트로 first 기준 오름차순 정렬*/

    int tmp = meet[n-1].first;
    for (int i = n - 2; i >= 0; i--) { // 시작 시간이 가장 늦은 것부터 탐색
        if (tmp >= meet[i].second) { // 현재 회의 시작 시간 >= 이전 회의 종료 시간
            cnt++;
            tmp = meet[i].first;
        }
    }
    printf("%d\n", cnt);
}​