본문 바로가기
프로그래밍/알고리즘 문제풀이

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

by 엽기토기 2020. 8. 6.
반응형

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

1931번: 회의실배정

1931번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 회의실배정 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 29402 8148 6076 28.732% 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것...

www.acmicpc.net

회의실배정 성공

시간 제한

메모리 제한

제출

정답

맞은 사람

정답 비율

2 초

128 MB

29402

8148

6076

28.732%

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> vec;
int comp(pair<int,int>a, pair<int, int>b) {
	if (a.second < b.second) return true;
	else if (a.second == b.second) return a.first < b.first;
	else return false;
}
int main() {
	int n;
	cin >> n;
	int a, b;
	
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		vec.push_back({ a,b });
	}
	sort(vec.begin(), vec.end(),comp);  
	int t = 0;
	int cnt = 0;
	for (int i = 1; i < vec.size(); i++) {
		if (vec[t].second <= vec[i].first) {
			t = i;
			cnt++;
		}
	}
	cout << cnt+1;
}
반응형