no.1931 회의실 배정

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


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N;
	cin >> N;
	vector<pair<int, int>> v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i].second >> v[i].first;
	}
	sort(v.begin(), v.end());
	int cnt = 1;
	int end = v[0].first;
	for (int i = 1; i < N; i++) {
		if (v[i].second >= end) {
			cnt++;
			end = v[i].first;
		}
	}
	cout << cnt << '\n';
	return 0;
}

 

문제분석

회의가 겹치지 않도록 최대한 많은 회의를 배정하는 문제이다.

즉 회의들을 정렬한 후, 회의를 살펴보면서 회의의 시작 시간이 현재 하고 있는 회의의 끝나는 시간보다 같거나 이후이면

갱신을 해주면 된다.

 

vector의 pair를 이용해서 간단하게 풀 수 있는데 

몰랐으면 매우 골치아플뻔한 문제이다. 

1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

이런 입력값을 pair로 받았은후 

정렬 해주면 

(여기서는 2번째 값을 기준으로 정렬하고 있다)

 

(4, 1)
(5, 3)
(6, 0)
(7, 5)
(8, 3)
(9, 5)
(10, 6)
(11, 8)
(12, 8)
(13, 2)
(14, 12)

 

이런식으로 정렬이 되고 

첫번째인 4시 이후에 시작하는 회의는 (5,7)->(8,11)->(12,14)로 진행될것이다 

for (int i = 1; i < N; i++) {
	if (v[i].second >= end) {
		cnt++;
		end = v[i].first;
	}
}