BOJ : 1931 회의실 배정

greedy algorithm

제일 어렵다. 그 때 그 때 가장 최적의 선택을 하는 것. 이중 for 문으로 모든 경우의 수를 찾아주는 순간 시간초과가 걸린다.

회의실 배정의 경우, 회의의 시작시간과 끝시간을 이용하여 가장 많은 회의를 할 수 있는 경우의 수를 찾는 것.

그 순간부터 시작할 수 있는 회의들 중에 가장 빨리 끝나는 회의를 찾는 것이 키 포인트였다.

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
nums = [list(map(int, list(input().strip().split()))) for _ in range(n)]

nums.sort(key = lambda x: (x[1],x[0]))
arr = [nums[0]]
for i in range(1, len(nums)):
    if arr[-1][1] <= nums[i][0]:
        arr.append(nums[i])
print(len(arr))