BOJ1931_회의실 배정

회의실 배정

A. 최대 사용할 수 있는 회의의 최대 개수를 구하라

how

1. 가장 짧은 구간을 갖는 회의를 진행(X)
2. 시작시간이 빠른 순으로 진행(X)
3. 끝나는 시간이 빠른 순으로 진행(O)

증명

• 만약 회의 시간이 있고 가장 빨리 끝나는 회의가 K라고 할 때. 이 회의 이후로의 시간만큼 사용할 수 있다.

• 그런데 만약 k보다 늦게 끝나는 회의 K'가 있을 때 K' 이후로의 시간만큼 사용할 수 있다.

• K'를 선택하게 되면 이 이후로의 시간이 K시간에 끝냈을 때 보다 범위가 더 적어진다.

  

• k에 끝나는 회의를 고르는것이 k'에 끝나는 회의를 고르는것보다 최적의 방법이라는 것을 반박하기 위해서는 L이라는 남은 시간보다 L'라는 남은시간에 회의들을 배치하는것이 더 많은 회의를 넣을 수 있다는 것을 증명해야한다.

Q. 과연 같은 회의목록들을 가지고 더 적은 타임에 많은 회의들을 넣는것이 가능할까?

• 당연히 불가능 하다.

따라서 항상 가장 빨리 끝나는 회의를 선택하는것이 최적의 해를 도출해낸다고 볼수 있다.