섹션 9. Greedy Algorithm 2. 회의실 배정

문제

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

입력

• 첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데
• 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 회의시간은 0시부터 시작한다.
• 회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.

출력

• 첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

입출력 예제

---

풀이방식

이번 문제는 그리디 알고리즘에 대한 문제이다.

그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

---

설계과정

1. 끝나는 시간을 기준으로 오름차순 정렬한다.

2. 끝나는 시간이 동일하면 시작하는 시간으로 오름차순 정렬한다.

3. Time 객체와 arr 배열을 하나씩 비교해서 시작 시간이 끝나는 시간보다 크거나 같으면 cnt를 누적한다.

4. Time 객체의 끝나는 시간으로 변수 값을 초기화하며 for문을 수행한다.

5. cnt를 출력한다.

---

풀이과정

1. 각 변수들을 선언한다.

• 시작과 끝나는 시간을 갖고 있는 클래스 Time를 가진 ArrayList 배열  arr[ ] 을 선언한다.
• 시작 시간을 의미하는 변수 start 을 선언한다.
• 끝나는 시간을 의미하는 변수 end 을 선언한다.

2. 각 회의의 시작과 끝 시간을 가지고 있는 클래스 Time를 선언하고, 오름차순으로 정렬한다.

 

3. 만약 끝나는 시간과 시작하는 시간이 동일하다면 시작 시간으로 오름차순 정렬한다.

 

4. 배열을 오름차순으로 정렬한다.

• Collections.sort() : 오름차순으로 정렬해준다.

5. for문을 통해 Time 객체와 arr 배열을 각각 비교해서 시작 시간이 끝나는 시간보다 크거나 같으면 cnt를 누적한다.

 

6. Time 객체의 끝나는 시간으로 변수 값을 초기화하며 for문을 수행한다.

 

7. 누적된 cnt를 출력한다.

 

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.