백준 19598 최소 회의실 개수 c++

문제

서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N이 너무 커서 괴로워 하는 우리 서준이를 도와주자.

입력

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

출력

첫째 줄에 최소 회의실 개수를 출력한다.

예제 입력 1 복사

3
0 40
15 30
5 10

예제 출력 1 복사

2

2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의를 진행할 수 없고 3개 이상의 회의실로 3개 회의를 모두 진행할 수 있지만 최소 회의실 개수를 구해야 하기 때문에 2가 정답이 된다.

예제 입력 2 복사

2
10 20
5 10

예제 출력 2 복사

1

 

문제 유형 : 그리디 알고리즘

 

처음에 priority queue를 사용하지 않고 벡터를 사용해서 정렬을 한 뒤 

만약에 이전 벡터의 범위 안에 현재 벡터의 범위가 들어가면 모두 겹치는걸로 판단해서 ++를 해 주었다 문제의 테스트 케이스들은 통과를 했지만 만약에  

0 10

5 20

15 25

같이 값이 들어왔을 때 내가 만든 공식대로하면 무조건 3이 된다 . 하지만 이것을 0 10 그리고 15 25를 하나로 보고 5 20을 하게 된다면

최소 회의실은 2개가 된다 즉 0 10을하고 10을 넘는 15로 시작하는 값이 들어왔을 때 하나로 보아야하는데 나는 무조건 3개로 보는게 문제였다. 도저히 방법이 떠오르지 않아서 또 블로그를 참고하였다 priority queue를 이용하여서 끝나는 지점을 다 오름차순으로 관리를 한다 

그리고 pq.top()보다 크거나 같은 시작지점이 들어오면 pq.top()을 pop() 해 준다. 그러면 pop된 회의 시간보다 작은 시간이 들어올리 없으니 (회의들의 시작시간을 오름차정렬을 했다) 그리고 for문에서 pq.size()가 가장 컸던 지점을 max로 관리를 해서 그 값을 출력을 해 준다. 

 

1 . 정렬된 pq의 가장 작은 회의 종료 시간보다 큰 시작시간이 들어온다 -> pq의 top을 pop해준다 

2. 정렬된 pq의 가장 작은 회의 종료 시간보다 작은 값이 들어온다 -> pq.push(해당 종료시간)을 해 준다.

 

작은값이 들어오면 계속해서 pq의 사이즈가 증가를하고 큰값이 들어오면 순차적으로 회의가 종료 됐다고 간주하고 그 회의를 종료시킨다(즉 pop해준다) 그리고 다음 회의종료시간보다 큰값이 들어오는지 작은값이 들어오는지 판별한다 . 

하 어렵구만

코딩의 세계는 멀고도 험하다 휴.. 진짜 ... 골드 2면 뭐하냐 .. 제대로 푸는게 거의 없는데 휴..... 분발하자 김준형

소마 합격 하겄냐