백준 1931번 회의실 배정 JAVA

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

 

요구사항 정의

• N <= 10^5
• 회의가 겹치지 않게 회의의 최대 개수
• 회의 시작시간 = 종료 시간인 경우 존재

 

풀이방법

처음에 풀고 아이디어가 떠오르지 않아 풀이를 본 문제이다.

 

그리디 방식으로 문제를 풀려고 하면 다음과 같이 풀것같다.

 

1. "시작 시간"이 작은 순으로 먼저 세기 : 조건에 맞지않다. 0-12와 같이 끝 시간이 매우 긴 회의가 먼저 나올 수 있다. 

2. "종료 시간"이 가장 작은 순으로 먼저 세기 : 가능성 존재

3. "시작-종료 시간의 차이"가 가장 작은 순으로 먼저 세기 : 가능성 존재, 하지만 구현 난이도가 높을 것으로 예상.

 

2번 방법으로 구현한다고 할 때 

생각해야하는 엣지 케이스는 회의 시간시작 = 종료 시간인 경우이다.

 

단순히 종료 시간으로만 정렬하게 된다면 아래 두 케이스는 서로 다른 결과를 출력한다.

2
1 4
4 4

// 정렬 결과
// 1 4
// 4 4
// 최대 회의 개수 : 2

2
4 4
1 4

// 정렬 결과
// 4 4
// 1 4
// 최대 회의 개수 : 1

 

따라서 종료 시간이 같다면 시작 시간이 작은 것부터 카운트한다.

 

 

그리디의 대다수의 문제는 정렬을 요구하는 문제들이 많은 것같다.

어떤 것을 정렬해야할지 가설을 세우고 반례를 찾아서 지워가는 능력이 필요한 것같다.

 

시간복잡도

정렬 로직이 있으므로 O(NLogN)

 

코드