탐구과정
기본적으로 짧은 회의 시간을 가지는 회의가 배정받아야 많은 회의를 진행할수있을것이다.
하지만 회의시간만으로 비교를 하는것이 아닌 시작시간과 종료시간이 있어 효율적으로 배치해야함
시작시간을 기준으로 정렬된 회의 전체 배열을 순환하며 실시간으로 현재 배정된 회의의 남은 시간과 다음 원소의 회의시간을 비교해 짧은 회의로 교체하며 알고리즘 상 조건이 될때 확정을 하여 카운트를 시켜주었다.
전체코드
from sys import stdin as s
# s = open("input.txt", "rt")
N = int(s.readline()) #회의수
arr = []
for _ in range(N): #배열 생성
t1, t2 = map(int, s.readline().split())
arr.append((t1, t2))
arr.sort(key=lambda x: x[0]) #시작시간으로 오름차순 정렬
# print(arr)
mo = arr[0][1]-arr[0][0] # mo : 맞다은 원소의 시작시간 차이
count = 1 #count 변수 : 회의실이 배정된 횟수, 1인 이유 = 아래 로직상 마지막 회의실 배정 카운트가 안되기에 미리 해줌
to = arr[0][0] #바로 전원소의 시작시간
#배정 알고리즘
for t1, t2 in arr: #정렬된 배열 순환
mo -= t1-to #시작시간 차이만큼 제해줌
to = t1
m = t2 - t1 #현재 선택된 원소의 회의시간
if m < mo: #이전 회의시간보다 작으면 회의를 교체함 (짧게 걸리는 회의로 교체, 하지만 확정은 아직 아님)
mo = m; continue
if mo <= 0: #mo가 0이하가 된다는것 = 현재 배정된 회의가 최선의 수, 그러므로 본 회의를 확정, 카운트
count += 1
# print("count up.")
mo = m #현재 원소로 회의를 새로 올린다 -> 이후 앞선과정 반복
print(count)
수일동안 고민했는데 답이 안나온다 70 80프로에서 오답 발생. 찾은 반례들은 통과하는데 오류뜨는 반례를 아직 못찾았다
----수정: 반례 발견
3
0 0
0 0
0 0
---
3
3
4 4
3 4
2 4
---
2.
