그리디 알고리즘

회의실 배정

4gats 2023. 5. 11. 21:00

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

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

1. 일찍 시작하는 회의부터 배정

2. 짧은 회의

 

정답은 빨리 끝나는 회의!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n, end, begin;
 
    vector<pair<int, int>> schedule;
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> begin >> end;
        schedule.push_back(make_pair(end, begin)); 
        // 거꾸로 넣는다! 빨리 끝나는 회의가 중요하므로
    }
 
    sort(schedule.begin(), schedule.end());
 
    int time = schedule[0].first;  // 종료 시간
    int count = 1;
    for (int i = 1; i < n; i++)
    {
        if (time <= schedule[i].second)
        {
            count++;
            time = schedule[i].first;
        }
    }
 
    cout << count;
}
cs