排程問題1：晚了就不要

前言

情境 - 晚了就不要

• 每項工作一樣重要。
• 主管只在意期限內完成的工作。
• 逾期的工作就不要了，沒人在意。

解題思路

一、簡化問題

二、排程方法

1. 將所有工作按 deadline 早晚排序
2. 依序將排序好的工作，一次一個排入行程表
3. 若排入的工作逾期，就從行程表中刪掉耗時最長的工作

1. 送餐 (7/3)
2. 擦窗 (7/4)
3. 掃地 (7/7)
4. 洗碗 (7/8)

結論

1. 將所有工作按 deadline 早晚排序
2. 依序將排序好的工作，一次一個排入行程表
3. 若排入的工作逾期，就從行程表中刪掉耗時最長的工作

附件

import datetime
import heapq

TODAY = '2023-07-01'
TASKS = [
  ('Clean Windows', 3, '2023-07-04'),  # (task_name, days, deadline)
  ('Sweep Floor',   2, '2023-07-07'),
  ('Wash Dishes',   3, '2023-07-08'),
  ('Deliver Food',  1, '2023-07-03'),
]

# preprocess
today = datetime.date.fromisoformat(TODAY)
tasks = [(t[0], t[1], datetime.date.fromisoformat(t[2])) for t in TASKS]

# step 1, sort by deadline
tasks.sort(key=lambda task: task[2])

# step 2 and 3
schedule = []
begin_date = today + datetime.timedelta(days=1)
for task in tasks:
  heapq.heappush(schedule, (-task[1], task))
  begin_date += datetime.timedelta(days=task[1])
  print('Add:   ', task[0])
  if (begin_date - datetime.timedelta(days=1) > task[2]):
    removed_task = heapq.heappop(schedule)
    begin_date = begin_date - datetime.timedelta(days=task[1])
    print('Remove:', task[0])

# print schedule
begin_date = today + datetime.timedelta(days=1)
schedule.sort(key=lambda t: t[1][2])
print('My schedule:')
for task in schedule:
  print(begin_date, 'start to:', task[1][0])
  begin_date += datetime.timedelta(days=task[1][1])

$ python schedule_case1.py
Add:    Deliver Food
Add:    Clean Windows
Remove: Clean Windows
Add:    Sweep Floor
Add:    Wash Dishes
My schedule:
2023-07-02 start to: Deliver Food
2023-07-03 start to: Sweep Floor
2023-07-05 start to: Wash Dishes