알고리즘

[백준, 파이썬, 1931번] 회의실 배정

hminor 2023. 8. 28. 10:48

풀이

  • 이런 회의실 배정과 같은 문제는 마치는 시간부터 접근하면 
  • 쉽게 해결할 수 있기에 정렬을 한 다음 풀기
    • 정렬시 마치는 시간을 기준으로 정렬 한 뒤
    • 같은 값이 있는 경우엔 시작 시간을 기준으로 한 번 더 정렬하여 해결
  • 그래서 현재 result에 있는 시작시간 보다 현재 li의 마치는 시간이 작거나 같을 경우엔 새롭게 추가
  • 아닐 경우엔 아래의 조건처럼 한번 더 조건 분기를 거친 다음 교체하여 해결
import sys
input = sys.stdin.readline
n = int(input())
li = sorted([list(map(int,input().rstrip('\n').split())) for _ in range(n)], key= lambda x: (x[1],x[0]), reverse=True)
result = [li[0]]
for i in range(1,n):
    if result[-1][0] >= li[i][1]: result.append(li[i])
    else:
        bf = result[-1][1]-result[-1][0]
        at = li[i][1]-li[i][0]
        if bf > at and result[-1][1]>=li[i][1] and result[-1][0]<=li[i][0]: result[-1] = li[i]
print(len(result))

'알고리즘' 카테고리의 다른 글

[백준, 파이썬, 1764번] 듣보잡  (0) 2023.08.29
[백준, 파이썬, 1026번] 보물  (0) 2023.08.29
[백준, 파이썬, 11399번] ATM  (0) 2023.08.28
[백준, 파이썬 , 10817번] 세 수  (0) 2023.08.28
[백준, 2468번] 안전 영역  (2) 2023.08.23