设计一个任务调度算法，用于确定哪些任务在同一时间段内发生了重叠。每个任务都有一个开始时间和结束时间。

描述：

需要设计一个任务调度算法，用于确定哪些任务在同一时间段内发生了重叠。每个任务都有一个开始时间和结束时间。需要设计一个方法来找出所有相互重叠的任务对，以便进行合理的资源分配或调整。

要求：
使用图的拓扑排序的概念来处理任务调度，确定任务的依赖关系并找出重叠。

示例：

假设你有以下任务：

• 任务1：从09:00开始，到10:00结束。
• 任务2：从09:30开始，到10:30结束。
• 任务3：从10:00开始，到11:00结束。

在这个任务调度中，你会发现：

• 任务1和任务2在09:30到10:00期间重叠。
• 任务2和任务3在10:00到10:30期间重叠。

因此，重叠任务对为（1, 2）和（2, 3）。

# 示例数据

tasks = [
   {"task_id": 1, "start": "09:00", "end": "10:00"},
   {"task_id": 2, "start": "09:30", "end": "10:30"},
   {"task_id": 3, "start": "10:00", "end": "11:00"}
]

解题思路

目标：
确定哪些任务在时间上发生了重叠，并找出所有重叠的任务对。

步骤：

1. 定义任务：每个任务都有一个开始时间和结束时间。
2. 构建事件列表：将每个任务的开始时间和结束时间视为事件。每个事件可以用一个元组表示，其中包括时间、事件类型（开始或结束）和任务ID。示例：对于任务 {"task_id": 1, "start": "09:00", "end": "10:00"}，会生成两个事件：("09:00", "start", 1) 和 ("10:00", "end", 1)。
3. 排序事件：按时间对事件进行排序。对于相同的时间，结束事件应排在开始事件之前。这是因为我们希望在处理开始事件时已经处理完了同一时间的结束事件，从而准确反映当前活动的任务。
4. 初始化数据结构：使用一个集合来跟踪当前活动的任务。这个集合会存储所有当前正在进行的任务的ID。初始化一个空列表来存储重叠任务对。
5. 处理事件：遍历排序后的事件列表：处理开始事件：遇到开始事件时，将当前任务添加到活动任务集合中。检查活动任务集合中的所有任务，记录与当前任务有重叠的任务对。处理结束事件：遇到结束事件时，从活动任务集合中移除当前任务ID。
6. 记录结果：将所有发现的重叠任务对存储在结果列表中。
7. 输出结果：返回包含所有重叠任务对的列表。

python

import xbot

from xbot import print, sleep

from .import package

from .package import variables as glv

from collections import deque

def find_overlapping_tasks(tasks):

   # 创建事件列表，每个事件包含时间、事件类型（开始或结束）和任务ID

   events = []

   for task in tasks:

       events.append((task["start"], "start", task["task_id"]))

       events.append((task["end"], "end", task["task_id"]))

   # 按时间排序事件，时间相同的情况下，结束事件排在前面

   events.sort(key=lambda x: (x[0], x[1] == "start"))

   # 使用集合来跟踪当前活动的任务

   active_tasks = set()

   overlapping_tasks = []

   # 处理事件

   for event in events:

       time, type_, task_id = event

       if type_ == "start":

           # 当前任务开始时，检查当前活动任务与新任务的重叠

           for active_task in active_tasks:

               overlapping_tasks.append((task_id, active_task))

           active_tasks.add(task_id)

       elif type_ == "end":

           # 当前任务结束时，从活动任务集合中移除

           active_tasks.remove(task_id)

   return overlapping_tasks

# 示例数据

tasks = [

   {"task_id": 1, "start": "09:00", "end": "10:00"},

   {"task_id": 2, "start": "09:30", "end": "10:30"},

   {"task_id": 3, "start": "10:00", "end": "11:00"}

]

# 查找重叠任务对

overlapping_tasks = find_overlapping_tasks(tasks)

print(overlapping_tasks)