문제

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

입력

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

출력

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

---

1. 해결방법 및 소스코드

• 최소 힙을 기반으로 한 우선순위 큐(Priority Queue)를 이용하였다.
• 회의목록을 받았을 때, 끝나는 시간이 빠른 순으로 정렬해야 회의목록을 훑어내려가면서 더 많은 회의들을 진행할 수 있겠다는 생각을 했다.
• 만약 끝나는 시간이 같다면 시작하는 시간이 빠른 순으로 정렬해야 시작시간과 끝 시간이 같은 회의가 나와도 그것을 카운트하고 넘어갈 수 있다.
• 따라서, 우선순위 큐에서 greater<pair<int, int>>를 사용할 것이기 때문에 원소들을 받을 때 pair로
  (끝시간, 시작시간) 을 받았다.
• 마지막으로 담은 회의의 끝 시간을 저장하여 그 다음 회의시작시간이 그 이후인지를 판별한 후 카운트를 올려주고, 그 회의를 큐에서 pop한다. 만약 그 다음 회의시작시간이 마지막으로 담은 회의의 끝 시간보다 이르다면 카운트 해주지 말고 그저 큐에서 pop만 하면 된다.

#include <iostream> #include <queue> using namespace std; int main() { int N, start, end; int count = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> confList; scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%d %d", &start, &end); confList.push(make_pair(end, start)); } start = 0, end = 0; while (!confList.empty()) { //만약 회의실 우선순위 큐에서 가장 위에있는 회의의 시작시간이 //현재 가장 마지막으로 끝난 회의의 시간보다 뒤라면 그 회의는 시작 가능하다. if (confList.top().second >= end) { start = confList.top().second; end = confList.top().first; count++; confList.pop(); } else { confList.pop(); } } printf("%d\n", count); }