beeimp
BeeImp
beeimp
전체 방문자
오늘
어제
  • 분류 전체보기 (110)
    • Program_Language (17)
      • Python (13)
      • Go (0)
      • JavaScript (4)
      • TypeScript (0)
      • Rust (0)
      • Solidity (0)
    • OS (8)
      • UNIX&LINUX (7)
      • Windows (0)
      • MacOS (1)
    • Front-End (19)
      • Svelte (19)
      • React (0)
    • Blockchain (6)
      • Bitcoin (0)
      • Ethereum (1)
      • Klaytn (0)
      • Project (5)
    • Data Structure&Algorithm (11)
      • Greedy (7)
      • Dynamic Programming (1)
      • Sort (0)
      • DFS & BFS (2)
      • Recursive (1)
    • Security (0)
      • SDP (0)
      • Authentication (0)
    • Network (3)
      • OpenWrt (0)
      • SDN&NFV (1)
    • Git (5)
    • IT_News (0)
    • 베타 학습단 (12)
      • SQL (12)
    • Project (1)
    • Issues (1)
    • Reviews (3)
    • I Learned (23)
      • TIL (23)
      • WIL (0)
    • Other (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • PYTHON
  • greedy
  • blockchain
  • svelte
  • Ethereum
  • Nest.js
  • 블록체인
  • mysql
  • jenkins
  • Docker
  • github
  • sql
  • Git
  • 탐욕법
  • 기초
  • react
  • ubuntu
  • typescript
  • javascript
  • solidity

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
beeimp

BeeImp

Data Structure&Algorithm/Greedy

강의실 - [백준 1374번]

2021. 7. 14. 17:46

강의실 - 백준 1374번

문제

  • N개의 강의
  • 최대한 적은 수의 강의실을 사용하여 모든 강의 진행
  • 한 강의실에서 동시에 강의 진행 불가
  • 종료시간과 시작시간이 같아도 상관 없음
  • 필요한 최소 강의실의 수 출력

입력

  • 첫째 줄 - N : 강의 갯수(1 <= N <= 100,000)
  • 둘째 줄부터 각 줄은 순서대로 강의 번호, 강의 시작 시간, 강의 종료시간
  • 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수

출력

  • 첫째 줄에 필요한 최소 강의실 개수 출력

코드

import sys
from queue import PriorityQueue # 우선순위 큐


def countClass(schedules):
  result = 0

  schedules = sorted(schedules, key=lambda s: s['startTime']) # 시작 시간 오름차순으로 정렬

  classes = PriorityQueue() # 우선순위 큐 선언

  for schedule in schedules:
    if not classes.empty() : # 사용하는 클래스가 있다면
      endTime = classes.get() # 클래스 큐 값 반환
      if endTime > schedule['startTime']: # 다음 강의가 가장 빨리 끝나는 클래스의 강의보다 빠르다면
        classes.put(endTime) # 클래스 추가
        result += 1

    else:
      result += 1 # 사용하는 클래스가 없어 결과값 1 추가

    classes.put(schedule['endTime']) # 우선순위 큐에 끝나는 시간 추가

  return result

N = int(sys.stdin.readline()) # 강의의 개수
schedules = []
for _ in range(N):
  number, startTime, endTime = map(int, sys.stdin.readline().split())
  schedules.append({"number": number, "startTime": startTime, "endTime": endTime})
print(countClass(schedules))

'Data Structure&Algorithm > Greedy' 카테고리의 다른 글

전자레인지 - [백준 10162번]  (0) 2021.07.14
세탁소 사장 동혁 - [백준 2720번]  (0) 2021.07.14
신입사원 - [백준 1946번]  (0) 2021.07.14
도서관 - [백준 1461번]  (0) 2021.07.14
배 - [백준 1092번]  (0) 2021.07.14
    'Data Structure&Algorithm/Greedy' 카테고리의 다른 글
    • 세탁소 사장 동혁 - [백준 2720번]
    • 신입사원 - [백준 1946번]
    • 도서관 - [백준 1461번]
    • 배 - [백준 1092번]

    티스토리툴바