[백준/1931] 회의실 배정(Python3)

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

문제 접근

해당 문제는 그리디 + 정렬 문제라고 생각한다.

정렬이라면 무엇을 기준으로 정렬할 지를 생각해야한다.

회의실 배정에 있어서 키 포인트는 종료 시간이다.

예를 들어, [0~10, 1~5, 2~3] 중에 어떤 회의를 선택해야 뒤에 더 많은 회의를 배정할 수 있을까?

당연히 종료 시간이 제일 먼저인 2~3을 배정해야 뒤에 더 많은 회의를 배정할 수 있을 것이다.

이를 이용해서 현 회의 종료 시간 <= 다음 회의 시작 시간를 검사하며 카운팅을 진행해 나가면 된다.

소스 코드

from typing import Deque, List, Tuple
from collections import deque


def count_possible_job(job_list: Deque[Tuple[int]]) -> int:
  count = 1

  cur_start, cur_end = job_list.popleft()
  while job_list:
    next_start, next_end = job_list.popleft()

    if cur_end <= next_start:
      cur_start, cur_end = next_start, next_end
      count += 1

  return count


def get_input() -> Deque[Tuple[int]]:
  n: int = int(input())
  job_list: List[Tuple[int]] = []

  for _ in range(n):
    start, end = map(int, input().split(" "))
    job_list.append((start, end))

  job_list.sort(key=lambda x: (x[1], x[0]))
  return deque(job_list)


print(count_possible_job(get_input()))