[Python/백준] 1931 : [그리디 알고리즘] 회의실 배정

1931 : [그리디 알고리즘] 회의실 배정

시간 제한: 2 Sec  메모리 제한: 128 MB

 

1931번: 회의실 배정

 

 

문제 설명

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

---

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

---

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

---

입력 예시

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

---

출력 예시

4

---

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

---

My 코드

# N: 입력 받을 회의 수
# I: 각 회의를 지칭

# 회의실 개수는 1개
# 회의 시작 시각과 끝나는 시각 동일할 수 있음
# 회의 끝나는 즉시 다음 회의 시작 가능
# 회의는 한번 시작되면 중간에 중단 불가 !!

N = int(input()) # 회의 수 입력 받기
meetings = [] # 회의 리스트
cnt = 0 # 회의 최대 개수 초기값 설정

for i in range(N): # N개씩
    begin, end = map(int, input().split()) # 각 회의 시작 시각(begin), 종료 시각(end) 입력 받아서
    meetings.append((begin, end)) # meetings(회의 정보) 리스트에 append

# 종료 시각을 기준으로 오름차순으로 먼저 정렬
# 다음으로 그 안에서 시작 시각을 기준으로 오름차순 정렬
meetings = sorted(meetings, key=lambda x: (x[1], x[0]))

meeting_end = 0 # 최종 회의 종료 시각 초기값 설정

for I in meetings: # I는 각 회의를 지칭
    begin = I[0]
    end = I[1]
    # 회의 시작 시각이 최종 회의 종료 시각보다 같거나 크면
    if begin >= meeting_end:
        cnt += 1 # 회의 개수 카운트
        meeting_end = end # 최종 회의 종료 시각(meeting_end) end 로 변경

print(cnt) # 회의 최대 개수 출력