백준 1931 회의실 배정

그리디 알고리즘 (고려해야 하는 것 : 현재 가장 좋은 상황 , 모순 여부 )

현재 가장 좋은 상황은 무엇일까 

	1.회의 시간이 짧은 회의부터
	2.빨리 시작하는 회의부터
	3.가장 적게 겹치는 회의부터
	4.빨리 끝나는 회의부터

이렇게 현재 가장 좋은 상황은 여러 가지 될 수 있다. 
하지만 모순이 없어야 함 ( 모순 : 가장 좋은 선택을 한 번 했을 땐 좋아 보이는데 
             두번 이상 한 이후에 돌아보니까 이 방법 말고 더 좋은 경우가 있었던 것임 )  

	
	1,2,3의 경우에는 모순이 생긴다. 
	그래서 4로 그리디 알고리즘을 해야 한다. ( 이 상황이 모순이 생기지 않는다는 것을 
                                      귀류법으로 증명을 할 수 있다는데 일단 패스)
	
4의 상황은 배낭에 물건을 넣는 상황과 같다. 
	
	무게 제한이 있는 배낭에 물건을 최대한 많이 넣고 싶을 때 
	가벼운 물건부터 넣는다. 그래야지 남은 무게가 가장 많고 
	남은 물건들을 많이 넣을 수 있는 가능성이 최대가 된다.
	
이 상황을 일반화하자면 
"무언가를 선택하면"  "무언가 자원이라고 할 수 있는 것이 감소"하는 상황이다.
	
	여기서는 회의를 선택하면 남은 시간이 감소하는 상황. 
	따라서 그때그때 선택할 수 있는 가장 빨리 끝나는 회의를 선택해야 
	남은 시간 즉 남은 자원이 최대가 된다. 


schedule=[]
for _ in range(n):
    schedule.append(list(map(int,input().strip().split())))
schedule.sort(key=lambda x:x[0])  #이렇게 안하면 (1,3) (5, 5) (3,5) 일 경우에 틀린다. 
schedule.sort(key=lambda x:x[1])

k=0  #회의가 끝나는 시간
count=0
for start,end in schedule:
    if start>=k:
        count+=1
        k=end