BOJ 1931 회의실 배정

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

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";
}