본문 바로가기
BOJ

BOJ 1931 회의실 배정

by 홍code 2022. 3. 10.

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

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

요약

한개의 회의실이 있다. 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";
}

 

'BOJ' 카테고리의 다른 글

BOJ 2212 센서  (0) 2022.03.10
BOJ 11000 강의실 배정  (0) 2022.03.10
BOJ 17509 And the Winner Is... Ourselves!  (0) 2022.03.10
BOJ 1449 수리공 항승  (0) 2022.03.10
BOJ 4796 캠핑  (0) 2022.03.10

댓글