[C++][백준 1931][그리디 알고리즘] 회의실배정 :: seoftware

!끝나는 시간을 기준으로 큐를 사용해서 풀었다!

문제

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

1931번: 회의실배정

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int N;
vector<pair<int, int>> time;
queue<pair<int, int>> q;

int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int start, end;
		cin >> start >> end;
		time.push_back({ end, start });
	}
	sort(time.begin(), time.end());
	for (int i = 0; i < N; i++) {
		q.push({ time[i].first, time[i].second });
	}
	int cnt = 0;
	while (!q.empty()) {
		int cur_y = q.front().first;
		int cur_x = q.front().second;
		q.pop(); cnt++;
		if (q.empty()) break;
		while (cur_y > q.front().second) {
			q.pop();
			if (q.empty()) break;
		}
	}
	cout << cnt << endl;
}

1. 끝나는 시간을 기준으로 sort 하기 위해 vector에 값을 넣을 때, {끝나는 시간, 시작시간}으로 넣었다

2. 끝나는 시간을 기준으로 정렬된 벡터를 큐에 넣었다

3. 큐에서 하나씩 꺼내며(while문) 시작시간이 자기보다 빠른 것은 제외시켰다.

4. 따라서 밖 while문이 시작될 때 pop되는 요소만 카운트(cnt++) 해주면 된다. 나머지는 속 while문에서 제거되므로(3).