BOJ 1931 회의실 배정

BOJ 1931 회의실 배정

문제링크 : https://www.acmicpc.net/problem/1931

요약

한개의 회의실이 있다. N개의 회의의 시작시간과 끝시간이 주어져 있을때, 회의가 겹치지 않게 회의실을 사용할수 있는 회의의 최대 갯수를 구하는 문제.

풀이

예제 값을 한번 그림으로 나타내보았다.

시작점을 기준으로 정렬해준다.

맨앞에 막대(회의시간)를 현재값으로 두고 순서대로 탐색하면서 현재의 막대의 끝점과 같은 시작점이 나오면 카운트해준다. 탐색중에 현재 막대의 끝점보다 더 빠른 끝점을 가진 막대가 나오면 현재 막대로 그것을 바꿔준다. 끝까지 탐색이 끝나면 카운트한 값을 출력해준다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int, int>>q;
pair<int, int>now;
int n,s,e,cnt=1;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s >> e;
		q.push_back({ s,e });
	}
	sort(q.begin(), q.end());
	now = q[0];
	for (int i = 1; i < q.size(); i++) {
		if (now.second > q[i].second)
			now = q[i];
		else if (now.second <= q[i].first) {
			now = q[i];
			cnt++;
		}
	}
	cout << cnt << "\n";
}