C++ / 백준 / 1931 / 회의실 배정

문제

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

1931번: 회의실 배정

문제풀이

시작시간순, 시작시간이 같다면 더 일찍 끝나는 순으로 정렬을 한다.

회의는 최소 한 번이므로 회의 개수를 1로 시작한다.

가장 빠르게 시작하면서 일찍 끝나는 회의의 시작시간을 front, 종료시간을 back으로 둔다.

모든 회의시간을 돌면서 back보다 종료시간이 빠른 회의가 있으면 back을 바꾼다.

회의 시작시간이 back 이상이면 회의 개수를 1 증가시키고 back을 해당 회의의 종료시간으로 바꾼다.

 

 

코드

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

bool Compare(pair<int, int>a, pair<int, int>b) {
	if (a.first == b.first)
		return a.second < b.second;
	else return a.first < b.first;
}

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

	int N = 0;
	cin >> N;

	vector<pair<int, int>>time(N, { 0,0 });
	int idx = 0;
	for (idx = 0; idx < N; ++idx)
		cin >> time[idx].first >> time[idx].second;

	sort(time.begin(), time.end(), Compare);
	int back = time[0].second;
	int answer = 1;
	for (idx = 1; idx < N; ++idx) {
		if (back > time[idx].second)
			back = time[idx].second;
		else if (back <= time[idx].first) {
			answer++;
			back = time[idx].second;
		}
	}
	cout << answer;
}