[백준][Python][1931][그리디] 회의실배정

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

1931번: 회의실배정

회의실/강의실/화장실 배정같은 이런 문제는 유명하고, 코테에도 나오고 하는 문제다. 

 

이런 문제는 끝나는 시간을 기준으로 정렬하라고만 알고있는데 왜 그런지 알아보자

 

1. 회의가 짧은 순서대로 배정하면?

|--------1------|     |--------2-------|

                      |----3----|

 

이런 순서가 나올 수 있으니까 안된다

 

2. 회의가 긴 순서대로 배정하면...은 의미없다

 

3. 회의가 일찍 시작하는 순으로 배정하면?

        |-1-|       |-2-|   |----3--|

  |---------------4---------------|

이런 문제에서 4를 선택하게 되나, 사실은 1,2,3을 가져갈 수 있다.

 

4. 회의가 일찍 끝나는 순으로 배정하면?

• 뒤에 남아있는 시간이 많아진다
  • 뒤에 넣을  수 있는 회의가 많아진다.

따라서, 회의가 일찍 끝나는 순으로 정렬하게 된다.

그럼, 끝나는 시간이 일치하면 왜 시작하는 시간 순으로 정렬해야 될까?

....그건 (5,6), (6,6) 같은게 문제상에 있을수 있어서다. 사실 (6,6) 이런게 있긴 하나..

 

 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

 

 

import sys

n = int(sys.stdin.readline())

reserv = []
numofresv = 0
latest = 0
for i in range(n):
	tmp = sys.stdin.readline().rstrip().split()
	tmp = [int(i) for i in tmp]
	reserv.append(tmp)


reserv.sort(key=lambda e:(e[1],e[0])) # 끝나는순, 시작하는 순 으로 정렬

latest = 0
numofresv =0
for i in range(0,n):

	if reserv[i][0] >= latest:
		numofresv+=1
		latest = reserv[i][1]
	

print(numofresv)