[ BOJ / C++ ] 1931번 : 회의실 배정

[ BOJ ] 1931번 : 회의실 배정

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

---

[  문제  ]

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

[  입력  ]

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

[  출력  ]

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

---

[  문제 접근 및 풀이  ]

회의의 시작 시간, 끝나는 시간을 vector에 넣은 후

회의가 끝나는 시간을 우선적으로 정렬하였으며

vector를 돌면서 회의가 가장 먼저 끝나면서도

시작 시간이 이전 회의가 끝나는 시간을 넘으면 cnt를 증가시켰다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
int x, y;
int n;
vector <pair<int, int>> V;
bool cmp(pair<int, int> a, pair<int, int>b);
void Q_1931();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Q_1931();
}
void Q_1931(){
	cin >> n;
	while (n--) {
		cin >> x >> y;
		V.push_back({x,y});
	}
	sort(V.begin(), V.end(), cmp);
	int cnt = 0;
	int Time = 0;
	for (auto i : V) {
		if (i.first>= Time) {
			cnt += 1;
			Time = i.second;
		}
	}
	cout << cnt;
}
bool cmp(pair<int, int> a, pair<int, int>b) {
	if (a.second==b.second) {
		return a.first < b.first;
	}
	return a.second<b.second;
}

---