< 백준 BaekJoon : 1931번 회의실 배정 > C++

 

<< 문제 >>

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

 

 

 

 

<< 풀이 >>

 

일단, 끝나는 시간을 먼저 고려했습니다.

시작 시간이 어떻든 끝나는 시간이 중요한거니,

끝나는 시간으로 정렬한 후 시작 시간이 이전에 고려한 끝나는 시간보다 이후인지만 생각하면 됩니다. 

 

<< 코드 >> 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


int main()
{
	int n;
	cin >> n;

	priority_queue<vector<int>> timeTables;
	
	for (int i = 0; i < n; i++)
	{
		int start, end;
	
		vector<int> timeTable;
		cin >> start >> end;
		
		// 끝나는 시간, 시작 시간
		timeTable.push_back(-end);
		timeTable.push_back(-start);

		timeTables.push(timeTable);
	}
	
	int cnt = 0;
	int lastTime = 0; // 마지막 끝난 시간
	while (!timeTables.empty())
	{
		if (-timeTables.top()[1] >= lastTime)
		{
			cnt++;
			lastTime = -timeTables.top()[0];
			timeTables.pop();
		}
		else {
			timeTables.pop();
		}
	}

	cout << cnt;
}

 

 

<< GitHub >>

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/1931.%E2%80%85%ED%9A%8C%EC%9D%98%EC%8B%A4%E2%80%85%EB%B0%B0%EC%A0%95

StudyAlgorithm_Part2/백준/Silver/1931. 회의실 배정 at main · J2on/StudyAlgorithm_Part2