[백준]1931번 회의실 배정 c/c++

문제

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

1931번: 회의실 배정

 

설명

 

 

회의시간들을 끝나는시간이 빠른순으로 정렬하고

끝나는시간이 동일하다면 시작하는 시간이 빠른순으로 정렬한다. (회의시작과 끝나는시간이 같을수도 있기 떄문에!!)

따라서 시작하는 시간, 끝나는 시간을 pair 에 반대로 저장해주었다.

 

t는 현재 시간이며, 0으로 초기화 해두고

제일 먼저 끝나는 회의시간을 t로 초기화 해두고 cnt값도 증가시킨다.

for문을 돌리며 다음 회의 시작시간 <= 회의 끝나는 시간 일때 cnt ++, t = s[i].second를 해준다.

그 경우가 아니라면 continue로 루프 처음으로 돌아간다.

 

 이렇게 for문을 마치고 나오면 cnt값은 4개, 즉 회의를 최대 4번 사용할 수 있다.

 

코드

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

pair<int, int> s[100005];
int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> s[i].second >> s[i].first;
	}
	sort(s, s + n);
	//끝나는 시간이 동일하다면 시작하는 시간이 빠른 순으로 배치해야 한다.
	//(2,2), (1,2) 가 있으면 (1,2) -> (2,2) 순으로 배치
	int cnt = 0;
	int t = 0;

	for (int i = 0; i < n; i++) {
		if (t > s[i].second) //회의가 끝나는 시간이 시작하는 시간보다 더 느릴때
			continue;
		cnt++;
		t = s[i].first;
	}
	cout << cnt;
	return 0;
}