APCS實作解題： 機器出租（112年1月）

2023 年 7 月 1 日
| 尚無留言

https://zerojudge.tw/ShowProblem?problemid=j608

題目：

  • 有N個活動要舉辦，每個活動開始結束時間是[ Li, Ri]
  • 有K台機器可開放租借。共可舉辦多少活動？

解題想法：

  • 紀錄表: 紀錄各機器被歸還時間（亦即活動的結束時間）
  • 每個活動依照結束時間排序，依序安排機器
  • 只要紀錄機器狀況的紀錄表第一個元素大於一活動的開始時間，此活動就可舉辦（有機器可借）
    • 將此活動的結束時間取代機器紀錄表中最接近它但小於他的時間

Python解：

import sys
import bisect

all_inputs = sys.stdin.readlines()
n, k = map(int, all_inputs[0].split())
start_time = list( map(int, all_inputs[1].split()) )
end_time = list( map(int, all_inputs[2].split()) )

data = sorted( zip(end_time, start_time))

E = [0]*k
ans =0

if k >=n:
  print(n)
else:

  for rr, ll in data:

    if ll > E[0]:
      ans +=1

      if ll > E[-1]:

        E[-1] = rr
      else:
        i1 = bisect.bisect_left(E, ll)
        E.pop(i1-1)
        E.append(rr)

  print(ans)
APCS