1931번 회의실배정 (V)

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

1. 문제 설명
 1) 회의 최대 개수 찾기
 2) 조건 : 시작하자마자 끝나는 경우: 시작시간 == 끝나는 시간 

2. 로직
 1) 우선순위 큐 이용한 오름차순 정렬(heap) (우선순위 작은 순서 순으로,  1순위. endTime , 2순위. startTime)
 2) 우선순위 큐로 정렬 된 n개의 인덱스들 중 첫번째 idx의 endTime과 두번째 idx의 firstTime 비교.
  중복범위가 아닌이상 카운팅하기.  (중복되지 않는 조건:  first.endTime <= second.startTime)
  카운팅한 부분과 중복된 부분은 pop함수로 후보를 줄여나갑니다.

3. example
Input:
8
1 3
2 3
3 3
4 4
5 5
6 6
7 7
3 6
answer: 6

#include<bits/stdc++.h>
using namespace std;
struct Node
{
	int startTime;
	int endTime;
	int period;
};

//우선 순위 q 구조체 타입 조건에 의한 비교
//조건 1 :  endTime이 짧은 순으로 우선순위정렬, 조건2 : endTime이 동일하면 start값이 낮거나 같은 값이 우선순위로 정렬
bool operator<(Node v, Node tar) { 
	if (tar.endTime < v.endTime) return 1; 
	else if (tar.endTime > v.endTime) return 0;
	return tar.endTime == v.endTime && (tar.startTime <= v.startTime);  
}
int main(void) {
	priority_queue<Node>meeting;
	int n;
	cin >> n;
	for (int x = 0; x < n; ++x) {
		int startTime, endTime, period;
		cin >> startTime >> endTime;
		period = endTime - startTime;
		meeting.push({ startTime,endTime,period }); // 우선순위 큐 에 원소 값 push하면 heap정렬이 자동으로 조성됨 그러나 기본이 내림차순이기에 operator 함수 내용안에 있는 조건에 의해 오름차순으로 정렬.
	}
	int cnt = 0;

	//사이즈가 1이면 진행할 필요없이 1 출력.
	if (meeting.size() == 1) {
		cout << 1;
		return 0;
	}
	
	//위 우선순위 큐 정렬에 의해 end값들이 작은 순으로 오름차순이 정렬되어진 상태이다.
	//첫번째의 인덱스[기준]와 두번째의 인덱스[타겟]를 비교하면서 두번째 인덱스가 첫번째 인덱스 범위에 포함되면 두번째 인덱스를 차차 삭제해나가면서
	// 범위 안에 포함되지 않는 부분들만 counting해나간다. 
	while (meeting.size() != 0) {
		//[기준] first
		int first_start = meeting.top().startTime;  
		int first_end = meeting.top().endTime;
		int first_period = meeting.top().period;
		meeting.pop(); // 후보 줄이기
		if (meeting.size() == 0) {
			break;
		}
		while (meeting.size() != 0) {
			//[타겟] second
			int second_start = meeting.top().startTime; 
			int second_end = meeting.top().endTime;
			int second_period = meeting.top().period;
			meeting.pop();  // 후보줄이기.
			if (first_end <= second_start) { // =을 사용한 이유 : (문제 조건) 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
				meeting.push({second_start, second_end, second_period}); // 첫번째 인덱스 내부에 두번째 인덱스가 포함되지 않으면 삭제된 두번째 인덱스를 기준으로 설정 위해 push.
				break;
			}
		}
	}
	cout << cnt << endl;
}

비율

로직 생각 : 구현 : 디버깅 = 5 : 2 : 3

 

회고

우선순위 큐 오랫만에 사용하여 개념을 상기했다.

다중 조건 오랫만에 하니 헷갈렸다. 많이 사용해보자.

 

 

다른 사람 풀이

https://instories.tistory.com/176