(cpp) Baekjoon 1931번 문제 ‘회의실배정’ - 그리디알고리즘

01 Oct 2022 on Programming Languages

Baekjoon 1931번 문제 ‘회의실배정’ - 그리디알고리즘

---

문제

풀이

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
using namespace std;

int n,ret;
int s, f;
vector<pair<int, int>> table;

int main() {

	//회의실 1개
	//회의 n개
	//각 회의가 안겹치면서 진행 가능한 최대수
	//한 회의 끝나는시간=다른회의시작시간 가능
	//현재시각 = 한 회의가 끝난 시간
	//그 시간보다 시작 시간이 나중인 회의 일정이 있으면 그걸 진행
	//현재시각 = 그 회의 끝난 시간으로 갱신
	//반복
	//더이상 현재 시각보다 늦은 회의 일정이 없을 때까지...

	cin >> n;
	ret = n;
	while (ret--) {
		cin >> s >> f;
		table.push_back(make_pair(f, s));
	}


	sort(table.begin(), table.end());  //f에 따라 정렬
	int ans = 1;
	int cur_time = table[0].first; //현재 시각은 첫 회의가 끝난 시간

	for (int i = 1; i < n; i++) {
		if (cur_time <= table[i].second) {
			ans = ans + 1;
			cur_time = table[i].first;
		}
	}
	cout << ans;
}